Given an array of integers, 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?

Example:

Input:

[4,3,2,7,8,2,3,1]

Output:

[5,6]

?

1 class Solution { 2 public: 3 vector<int> findDisappearedNumbers(vector<int>& nums) { 4 // put all numbers in correct positions 5 for (int i = 0; i < nums.size(); i++) { 6 while (nums[i] != -1 && i != nums[i] - 1) { 7 if (nums[i] == nums[nums[i] - 1]) { 8 nums[i] = -1; 9 break; 10 } 11 swap(nums[i], nums[nums[i] - 1]); 12 } 13 } 14 15 // put all vacant numbers into the result array 16 vector<int> result; 17 for (int i = 0; i < nums.size(); i++) { 18 if (nums[i] == -1) 19 result.push_back(i + 1); 20 } 21 return result; 22 } 23 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/amazingzoe/p/6018124.html

總結(jié)

以上是生活随笔為你收集整理的Find All Numbers Disappeared in an Array的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。