區別一、448題目沒有限制不能改變原來的數組，所以采用的是交換機制，不斷的將錯誤位置上的數據不斷的交換移動到本該屬于其的位置上去，則重新遍歷時，nums[i]!=i+1的數字即沒有出現的數字，但287題目則限制了不能改變原來的數組，所以不能采用交換機制的方法，方法類似采用查找循環鏈表的環入口的方法，或者可以采用利用二分查找的思想； 區別二、448題目中1-n之間重復的數字只出現了兩次，但是在287中則至少出現兩次 一、448題目 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input: [4,3,2,7,8,2,3,1]
Output: [5,6] 采用的方法是：不斷的將錯誤位置上的數據不斷的交換移動到本該屬于其的位置上去，則重新遍歷時，nums[i]!=i+1的數字即沒有出現的數字
//注意不斷的將錯誤位置上的數據不斷的交換移動到本該屬于其的位置上去，則重新遍歷時，nums[i]!=i+1的數字即沒有出現的數字 vector<int> findDisappearedNumbers(vector<int>& nums) { int len = nums.size(); vector<int> result; for(int i = 0; i < len; i++) { if(nums[i] == i+1) { continue; } else { while(nums[nums[i] - 1] != nums[i] ) { //int idx = nums[i] - 1; int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } } for(int i = 0; i < len; i++) { if(nums[i] != i+1) { result.push_back(i+1); } } return result; }二、287題目： Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), PRove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once. 二分查找：
int findDuplicate(vector<int>& nums) { //二分查找，思想利用下標來實現，諸如：1...10的數中，如果小于5的數目大于5，那么表明重復的數字一定在小于5的數目中，妙哉 int len = nums.size(); if(len == 0 || len == 1) return -1; int low = 0; int high = len - 1; while(low <= high) { int mid = low + (high - low) / 2; int count = 0; for(int i = 0; i < len; i++) if(nums[i] <= mid) count++; if(count > mid) high = mid - 1; else low = mid + 1; } return low; }尋找鏈表環入口的方法：
int findDuplicate(vector<int>& nums) { //像尋找單鏈表的環入口點的思路一樣，設置一塊一慢的指針，由于數組中存在重復節點，則可通過下標來聯想成鏈表 int len = nums.size(); if(len == 1 || len == 0) return -1; int slow = nums[0]; int fast = nums[slow]; //以下為求兩個指針第一次相遇的點 while(slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } //以下求重復元素的節點，即重復元素的入口節點 fast = 0; while(fast != slow) { fast = nums[fast]; slow = nums[slow]; } return slow; }新聞熱點
疑難解答
