[剑指Offer]---03数组中重复的数字与04二维数组中的查找

03数组中重复的数字

思路：哈希表，扫描数组里的每个数字，看哈希表里是否有这个数字，没有就将这个数字加进去，有的话，则该数字重复。时间复杂度是O（n）。

class Solution {
public:int findRepeatNumber(vector<int>& nums) {unordered_set<int>  record;for(auto iter=nums.begin();iter!=nums.end();++iter){int count=record.count(*iter);if(count==0){record.insert(*iter);}else {return *iter;}}return -1;}
};

04二维数组中的查找

思路：

    右上角遍历，时间复杂度O(n+m)

    如果该数字等于要查找的数字，查找过程结束；

    如果该数字大于要查找的数字，剔除这个数字所在的列；

    如果该数字小于要查找的数字，剔除这个数字所在的行

 

class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {if(!matrix.empty()){// 行列个数int row = matrix.size();int col = matrix[0].size();// 右上角坐标int x = 0;int y = col-1;while(x<row && y>=0){if(matrix[x][y] == target)return true;if(matrix[x][y] < target)++x;else--y;}}return false;}
};