1. 数组中重复的数字

开始，准备熬夜看发布会，开始前先来道题。这次准备开一个新的章节：查找算法，增加点新鲜感！第17题：数组中重复的数字。在没看高效算法下，大致思路是创建一个等空间大小的bool数组，依次遍历，但是这样时间复杂度和空间复杂度都很高。看了解析，一种做法是利用set，记录数组的各个数字,当查找到重复数字则直接返回。但是感觉还是不够好，方法二原地交换讲空间复杂度优化到了常数。可遍历数组并通过交换操作,使元素的 索引 与 值 一一对应(即nums[i]=i )。因而，就能通过索引映射对应的值，起到与字典等价的作用。

  1. class Solution {
  2. public:
  3.     int findRepeatNumber(vector<int>& nums) {
  4.         int i = 0;
  5.         while(i < nums.size()) {
  6.             if(nums[i] == i) {
  7.                 i++;
  8.                 continue;
  9.             }
  10.             if(nums[nums[i]] == nums[i])
  11.                 return nums[i];
  12.             swap(nums[i],nums[nums[i]]);
  13.         }
  14.         return -1;
  15.     }
  16. };

2. 二维数组中的查找

开始，第18题：二维数组中的查找。题目中的二维数组比较特殊，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。初步想法可以按照从上到下递增来筛选掉一些数字，若某一行的第一个数字都大于所给的数字，那么这一行都可以跳过了。早上写出来发现还是超时。看了解析，发现解析所给的方法太精妙，逆时针旋转旋转45度，形式就很类似二叉搜索树了。自己的思想对了一半，只是考虑到了行首元素大于目标值则跳过此行，从对角线开始，列尾元素小于目标则跳过此列。

  1. class Solution {
  2. public:
  3.     bool findNumberIn2DArray(vector<vector<int>> &matrix, int target) {
  4.         //左下方[i][j]开始
  5.         if (matrix.empty())
  6.             return false;
  7.         int i = matrix.size() - 1;
  8.         int j = 0;
  11.         while (i >= 0 && j <= matrix[0].size() - 1) {
  12.             if (matrix[i][j] == target)
  13.                 return true;
  14.             //上移
  15.             if (matrix[i][j] > target)
  16.                 i--;
  17.             //右移
  18.             if (matrix[i][j] < target)
  19.                 j++;
  22.         }
  23.         return false;
  24.     }

测试没问题，可是老出现错误，数组越界，一下午也没有debug出来。

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

用一个vector去当作备忘录，扫描一次，记录每一个字母出现的次数，然后再遍历一次，返回第一个出现次数为1的字符即可。
后面查资料学到了一点，用auto去写循环，可以适应各种数据类型还很简单。

  1. char firstUniqChar(string s) {
  2.     vector<int> dic(26, 0);
  3.     for (auto c : s) {
  4.         dic[c - 'a']++;
  5.     }
  6.     for (auto c : s) {
  7.         if (dic[c - 'a'] == 1)
  8.             return c;
  9.     }
  10.     return ' ';
  11. }

4. 在排序数组中查找数字 I

试着用上一题的思路写，但是发现问题在于上一题只是需要26字母，但是这次数字会很大。
之后用map去做，很简单，但是时间和空间效率都不够好。

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         map<int, int> nums_record;
  5.         for (int i = 0; i < nums.size(); ++i) {
  6.             nums_record[nums[i]]++;
  7.         }
  8.         return nums_record[target];
  9.     }
  10. };

5. 0～n-1缺失的数字

拿到这个题目，乍一想用一个map去做，但是空间复杂度和时间复杂度都达到了n。既然是查找章节，那么应该使用查找的算法，二分法应该是可以的。只是少一个数字，那么如果nums[m] == m，那么说明缺失的数字在右侧，否则不等就是在左侧。

  1. class Solution {
  2. public:
  3.     int missingNumber(vector<int>& nums) {
  4.         int i = 0, j = nums.size() - 1;
  5.         while(i <= j) {
  6.             int m = (i + j) / 2;
  7.             if(nums[m] == m) 
  8.                 i = m + 1;
  9.             else 
  10.                 j = m - 1;
  11.         }
  12.         return i;
  13.     }
  14. };

6. 旋转数组的最小数字

旋转数组，说白了就是两个有序对数组组成的。要找的就是分界点右边的那个数字。考虑数组中的最后一个元素x：在最小值右侧的元素，它们的值一定都小于等于x；而在最小值左侧的元素，它们的值一定都大于等于x。根据这一条性质可以通过二分查找的方法找出最小值。
使用二分法的时候,第一次失败了，原因是忽略了对于相等时候的判断.因为在相等时，无法判断mid是在最小数的左边还是右边，唯一可以知道的是，由于它们的值相同，所以无论high是不是最小值，都有一个它的“替代品”：mid，因此我们可以忽略二分查找区间的右端点。所以只需要将“high—”来缩小范围缩小范围即可。
在看官网解释的时候，这篇解析用了一系列图，理解起来十分简单，网址放在下面。
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui—16/

  1. class Solution {
  2. public:
  3.     int minArray(vector<int>& numbers) {
  4.         int i = 0;
  5.         int j = numbers.size()-1;
  6.         while(i<j){
  7.             int mid = (i+j)/2;
  8.             if(numbers[mid]>numbers[j])
  9.                 i= mid +1;
  10.             else if(numbers[mid]<numbers[j])
  11.                     j = mid;    //mid不能排除在外，不能j=mid-1
  12.                 else
  13.                     j--;
  14.         }
  15.           return numbers[i];
  16.     }
  17. };