[leetcode] 448. Find All Numbers Disappeared in an Array

[leetcode] 448. Find All Numbers Disappeared in an Array

Description

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~n。

对于每个数字nums[i]，如果其对应的nums[nums[i] - 1]是正数，我们就赋值为其相反数，如果已经是负数了，就不变了，那么最后我们只要把留下的整数对应的位置加入结果res中即可.

代码

class Solution {public: vector findDisappearedNumbers(vector& nums) { vector result; for(int i=0;i0){ nums[idx]=-nums[idx]; } } for(int i=0;i0){ result.push_back(i+1); } } return result; }};

参考文献

​​[LeetCode] Find All Numbers Disappeared in an Array 找出数组中所有消失的数字​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。