基础模板

找出重复的数字

13. 找出数组中重复的数字 - AcWing题库

这题数据量比较小，并且告诉了数据的大小范围，可以直接使用数组模拟也可以使用map来存储每一个数字出现的次数 遍历的时候就可以直接得到结果，如果每个数字出现的次数大于1，那么可以直接返回结果。

class Solution {
public:
int duplicateInArray(vector<int>& nums) {
    map<int,int> m;
    for (auto &num : nums) {
        if (num < 0 || num > nums.size() - 1)
            return -1;
    }
    for(auto& num : nums) {
        if(++m[num] > 1) return num;
    }
    // cout << endl;
    return -1;
}
};

不修改数组找出重复数字

14. 不修改数组找出重复的数字 - AcWing题库

注意题目给定的数据和范围，数组的长度是n+1，但是所有的数均在1~n的范围内，并且n>=1 当我们有3个苹果，但是只有两个盒子（并且每个盒子中至少要放一个时），那么肯定会有一个盒子里面要放两个苹果

那么这个题目，我们可以将数据范围分成两个部分：1~2/n和2/n + 1 ~ n这两个区间，如果某个区间的中的数据量超过了区间长度，那么这个区间内肯定有重复元素。然后不断缩减区间大小，直到最后区间长度为1，即为最后的答案

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while(l < r) {
            int mid = (r - l) / 2 + l;
            int temp = 0;
            for(auto& num : nums){
                if(num >= l && num <= mid) temp++;
            } 
            if(temp > (mid - l + 1)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

二维数组中的查找和替换

15. 二维数组中的查找 - AcWing题库

主要读清楚题目的意思，然后找到规律 对于最右上角的那个数来说：

1. 其左边的数一定比它小
2. 其下边的数一定比它大

也就是说，不妨将右上角的数记作cur

• 如果cur大于target，那么cur所在列的其他数也一定大于target
• 如果cur小于target，那么cur所在行的其他数也一定小于target

通过这种规律，就可以减少很多不必要的查找，从而快速找到答案

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        // m是列，n是行
        if (array.empty() || array[0].empty()) return false;
        int m = array[0].size();
        int i = 0, j = m-1;
        while(i < array.size() && j >= 0) {
            if(array[i][j] == target) return true;
            if(array[i][j] < target) {
                i++;
                continue;
            }
            if(array[i][j] > target) {
                j--;
                continue;
            }
        }
        return false;
    }
};