442. Find All Duplicates in an Array

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

想法

no extra space…

注意到 $ 1 <= a[i] <= n$

用下标对应的关系应该就可以了吧

答案

第一个AC的答案
噗，0.61% hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
                i--;                
            }
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == i+1)
                nums[i] = 0;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                nums.erase(nums.begin() + i);
                i--;                
            }
        }
        return nums;
    }
};

尽管是O(n)，但是应该是做了好多无用的事

回顾

唔，看了别人的答案，只是觉得，想法基本上是一样的，只是without extra space，自己也没有新开一个vector来存结果

有一些粗心，注意下标的一些获取！