行百里者半九十 —

行百里者半九十 —— 查找算法

------------恢复内容开始------------

剑指 Offer 03. 数组中重复的数字

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - II. 0～n-1 中缺失的数字

1、找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

该题有多种解法，要明确出题人的意图，是时间优先还是空间优先
1) 空间优先：空间O(1)，时间O(nLogn)
先排序，再查看相邻元素是否相同

 1 class Solution{
 2     public:
 3     int findRepeatNumber(vector<int>& nums) {
 4         sort(nums.begin(), nums.end()); 5         for(int i = 0; i < nums.size()-1; i++) {
 6             if(nums[i] == nums[i+1]){
 7                 return nums[i];
 8             }
 9         }
           return -1;
10     }
11 };

2) 时间优先：空间O(n)，时间O(n)

哈希表，每次存储时检查是否有重复的元素

 1 class Solution{
 2     public:
 3     int findRepeatNumber(vector<int>& nums) {
 4         unordered_map<int, int> mp;
 5         for(int i = 0; i < nums.size(); i++){
 6             if(mp.find(nums[i]) != mp.end()) return nums[i];
 7             else mp[nums[i]] ++;
 8         }
 9         return -1;
10     }
11 };

2、在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

该题一般是考察二分法时间复杂度O(logn), 空间复杂度O(1)

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int length = nums.size();
 5         int left = 0;
 6         int right = length -1;
 7         while(left < right) {  //非递减数组
 8             int mid = (left + right)/2;
 9             if(nums[mid] >= target) right = mid;
10             if(nums[mid] < target) left = mid;
11         }
12         int count = 0;
13         while(nums[left++] == target)
14             count++;
15         return count;
16     }
17 };

3、0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

 1 class Solution {
 2 public:
 3     int missingNumber(vector<int>& nums) {
 4         int length = nums.size();
 5         int left = 0;
 6         int right = length -1;
 7        
 8         while(left < right) {  //非递减数组
 9             int mid = (left + right)/2;
10             if(nums[mid] == mid) left = mid;  //注意是mid+1
11             else right = mid;
12         }
13         if(nums[left] != left )
14             return left;
15         else 
16             return left+1;   //0~n-1的数组，恰好n不在其中[0,1,2,3]
17         return -1;
18     }
19 };

对于有序的数组, 都应该想到用二分法搜索