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]
給定一個整數數組，其中1 ≤ a[i] ≤ n (n = 數組長度)，一些元素出現兩次，其他的出現一次。如果每個元素只出現一次，則元素與下標的關系為a[i] = i+1。
不使用額外的空間，O(n)的時間復雜度?？紤]在當前數組上進行操作，遍歷一遍該數組。如果滿足nums[i] == i+1的關系，則元素在正確的位置上，如果不滿足，則不斷的將錯誤位置上的元素移動到本該屬于其的位置上。重新遍歷時，nums[i]!=i+1的數字則是沒有出現過的元素。class Solution {public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; for(int i = 0; i < nums.size(); i++) { if(nums[i] == i+1) continue; else { while(nums[nums[i] - 1] != nums[i] ) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } } for(int i = 0; i < nums.size(); i++) { if(nums[i] != i+1) res.push_back(i+1); } return res; }};在網上看到另一種解法：不移動元素位置，使用正負號標記來確定該數字是否出現。 元素值的絕對值減一作為下標，該下標對應的值改為負值。 重新遍歷時，元素值為正數的，說明該下標加一的數字沒有出現。class Solution {public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; for (int i = 0; i < nums.size(); i++) { int index = abs(nums[i])-1; if (nums[index] > 0 ) { nums[index] *=-1; } } for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) res.push_back(i+1); } return res; }};新聞熱點
疑難解答
