题意：每行都是从小到大排好序的，且 每行第一个数比前一行最后的一个数大。
解法一：将一个二维数组当作一维数组来进行二分搜索，则left索引为0，right索引为 row*col - 1； 再将这个一维数组中的坐标映射到二维数组中， 即matrix[mid/col][mid%col].
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int row = matrix.size(), col = matrix[0].size(); int left = 0, right= row*col-1; while(left<=right){ int mid = left + (right-left)/2; if(target == matrix[mid/col][mid%col]) return true; else if(target < matrix[mid/col][mid%col]) right = mid-1; else left = mid+1; } return false; } };
二分搜索也可以这样写（但是比较慢）：
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int row = matrix.size(), col = matrix[0].size(); int left = 0, right= row*col-1; while(left<right){ int mid = left + (right-left)/2; if(target <= matrix[mid/col][mid%col]) right = mid; else left = mid+1; } if(matrix[left/col][left%col] == target) return true; return false; } };
解法二：先用二分搜索找到target的所在行，再对这个行进行二分搜索。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int row = matrix.size(), col = matrix[0].size(); int left = 0, right= row-1; while(left<right){ int mid = left + (right-left)/2; if( target<=matrix[mid][col-1]) right = mid; else left = mid+1; } if(matrix[left][col-1]==target) return true; int n = left; left = 0, right = col-1; while(left<right){ int mid = left + (right-left)/2; if( target<=matrix[n][mid]) right = mid; else left = mid+1; } if(matrix[n][left] == target) return true; return false; } };
将二维矩阵的右上角作为起点，当target > matrix[l][r]时：l++；target < matrix[l][r]时：r- -
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.empty() || matrix[0].empty()) return false; int row = matrix.size(), col = matrix[0].size(); int l = 0, r = col-1; //从右上角走 while(l<row && r>=0){ if(matrix[l][r] == target) return true; else if(matrix[l][r]> target) //向左走 r--; else l++; } return false; } };
这道题题意很难理解，set的意思是将（key , value , timestamp）存储起来；get是返回(key, timestamp_prev) 对应的value, 其中 timestamp_prev <= timestamp；若有多个这样的值，则返回最大的timestamp_prev对应的value；若没有这样的timestamp_prev，则返回空。
思路：
1）设计两个hash Table，一个存储<timestamp, value>, 另一个存储<key, <timestamp, value>>
2）对于插入操作，直接在对应的键中，添加对应的时间戳和值
3）对于查询操作，如果待查询的时间戳比set里最早的还要早，则返回空字符串。若大于等于最晚的，则返回最后一个对应的值。否则在时间戳数组中二分（upper_bound)，找到第一个严格大于当前查询时间戳的位置，然后返回上一个位置的值。
class TimeMap { public: /** Initialize your data structure here. */ //<key, <timestamp, value>> unordered_map<string, map<int, string>> s; TimeMap() { } void set(string key, string value, int timestamp) {
//插入操作 //s[key].emplace(timestamp, move(value));
s[key].emplace(timestamp, value); } string get(string key, int timestamp) { auto m = s.find(key);
//set中找不到key，返回空 if(m==s.end()) return "";
//将it赋值为 比timestamp大的第一个时间戳 auto it = m->second.upper_bound(timestamp);
//若it == 最早的时间戳，说明set里所有的时间戳都比timestamp大，找不到返回空 if(it == begin(m->second)) return "";
//否则返回it的前一个时间戳 return prev(it)->second; } }; /** * Your TimeMap object will be instantiated and called as such: * TimeMap* obj = new TimeMap(); * obj->set(key,value,timestamp); * string param_2 = obj->get(key,timestamp); */