【LeetCode】448. Find All Numbers Disappeared in an Array
【LeetCode】448. Find All Numbers Disappeared in an Array
韩旭051
发布于 2019-11-07 23:23:40
发布于 2019-11-07 23:23:40
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/102369510
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]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一个萝卜一个坑，不对付就换到自己的位置就行了。
要用while没换到底就一直换。
class Solution {
public:
void swap(vector<int>& nums , int i){
int t= nums[nums[i]-1];
nums[nums[i]-1]= nums[i];
nums[i]=t;
}
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n =nums.size();
for(int i=0;i<n;i++){
while(nums[i]!= nums[nums[i]-1]){
swap(nums,i);
}
}
vector<int> v;
for(int i=0;i<n;i++){
if(nums[i]!= i+1){
v.push_back(i+1);
}
}
return v;
}
};第一的代码 ，人家这个在我的个人理解看来很巧妙
这个位置应该有个数他没有换过去，而是置换成负数，这样表示这里应该有个数。时间复杂度就是1.空间复杂度也是1.满足题目要求没有任何多余的空间。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> result;
if(nums.empty())
return result;
for(int i = 0; i < nums.size(); i++){
nums[abs(nums[i]) - 1] = 0-abs(nums[abs(nums[i]) - 1]);
}
for(int i =0; i < nums.size(); i++){
if(nums[i] > 0)
result.push_back(i + 1);
}
return result;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录