448. Find All Numbers Disappeared in an Array

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]

解题思路：

参考了https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/481254/C++-solution-O(1)-Easy-7-lines-code

巧妙的改变数组本身的值。遍历整个数组，将数组的值作为索引，将对应索引位置的数组值变为负数，这样遍历一遍后，数组值为正的那个索引，比如nums[5] = 2, 则说明5没有出现过。在实际的应用中，如果数组的值可以随便改变，则可以使用此方法。

class Solution{public:    vector<int> findDisappearedNumbers(vector<int>& nums) {        vector<int> rlt;        for(int i=0; i<nums.size(); i  ) {            nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);        }        for(int i=0; i<nums.size(); i  ) {            if(nums[i]>0) {                rlt.push_back(i 1);            }         }        return rlt;    }};

Haskei发布了153 篇原创文章 · 获赞 29 · 访问量 10万私信关注来源：https://www.icode9.com/content-4-625151.html

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。