查找算法

03.数组中重复的数字

简单，使用hash表即可

• 一边填入hash表一边判断可以有效的节省空间

  class Solution {
  public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++){
            if(hash[nums[i]]){
                return nums[i];
            }
            hash[nums[i]]++;
        }
        return 0;
    }
  };

  53-1.在排序数组中查找数字

  这题用到二分法，先找右边界，在找左边界。边界确定就看特殊情况。注意，无论是左闭右开还是左闭右闭都是看l来确定边界

  class Solution {
  public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] >= target){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        int first = left; 
        left = 0, right = n;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left -first;
    }
  };

  53-2 0~n-1中缺失的数字

  笨蛋方法(引以为戒)

  class Solution {
  public:
    int missingNumber(vector<int>& nums) {
        if(nums[0] != 0){
            return 0;
        }
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != i){
                return i;
            }
        }
        return nums.size();
    }
  };

  连续两次都想到的是这种笨蛋方法，引以为戒

  二分法

  二分法，判断的依据是，nums[i]==i。这里没想出来太可惜了。返回值需要思考一下，我刚开始的时候返回的是nums[l]-1，没有考虑到数组越界的情况。因为求出来的l就是缺数的位置，直接返回l即可。

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

  04. 二维数组中的查找

  这一题和以前写过的一题非常的相似。想法非常类似，这是一个从右下递增的数组，选取右上的中间数，比目标数小则下移，比目标数大则左移。

  class Solution {
  public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0){
            return false;
        }
        int i = 0, j = matrix[0].size() - 1;
        while(j>=0&&i<matrix.size()){
            if(matrix[i][j] > target){
                j --;
            } else if (matrix[i][j] < target){
                i ++;
            } else {
                return true;
            }
        }
        return false;
    }
  };

  11. 旋转数组的最小数字(二分法/重点)

  本题对应leetcode的153和154两题。非常特殊，使用变化的边界来进行二分查找，主要问题是处理mid 与 r相等的情况。利用了旋转之后的数组最右值得特点，只要大于最右值得都是位于最小值左边，小于最右值得就在最小值或右边。相等的情况，可有可无，因为代表至少有两个值，右边界缩一位即可。

  class Solution {
  public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            }
            else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            }
            else {
                high -= 1;
            }
        }
        return numbers[low];
    }
  };

  50. 第一个只出现一次的字符

  非常简单，hash就解决了，也没有复杂度更小的方法。

  class Solution {
  public:
    char firstUniqChar(string s) {
        unordered_map<char, int> hash;
        vector<char> vec;
        for(auto it : s){
            if(hash[it] == 0){
                vec.push_back(it);
            }
            hash[it]++;
        }
        for(auto it : vec){
            if(hash[it] == 1){
                return it;
            }
        }
        return ' ';
    }
  };