442. Find All Duplicates in an Array
1. Description
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
2. Example
Example 1:
Input: [4,3,2,7,8,2,3,1]
Output: [2,3]
3. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
// vector<int> findDuplicates(vector<int>& nums)
vector<int> findDuplicates(vector<int>& m_nums) {
vector<int> duplicates;
for (auto num : m_nums) {
int positiveNum = abs(num);
if (m_nums[positiveNum - 1] < 0) {
duplicates.push_back(positiveNum);
} else {
// we iterate the vector and put every number to negative
// when we find a key's value is negative
// this key must has a duplicate
m_nums[positiveNum - 1] *= -1;
}
}
return duplicates;
}
};