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]
Solution
问题的关键是利用1->n的数字和总长度n的对应关系!!
不用额外空间进行记录出现过的数字方式 => 用出现的位置正负来记录!! 思路很巧妙
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int> &nums) {
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
int idx = abs(nums[i]) - 1;
nums[idx] = nums[idx] > 0 ? -nums[idx] : nums[idx];
}
for (int i = 0; i < nums.size(); ++i) if (nums[i] > 0) res.push_back(i+1);
return res;
}
};
类似的问题还有"找出重复数字","找出唯一不重复数字"
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论