1480. Running Sum of 1d Array - easy
문제
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.
제한사항
입출력 예
1
2
3
4
5
6
7
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
풀이
- Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
std::vector<int> res;
// nums의 값과 index를 매칭
// nums의 값에 대응하는 nums의 인덱스의 값(nums[nums[i]])을
// * -1 하여 해당 인덱스는 존재하는 것을 표시
// 최종적으로 nums에 남아있는 양수값의 값을 가진 인덱스들이
// nums 배열의 값에 존재하지 않는 인덱스가 된다.
for (auto i = 0 ; i < nums.size() ; ++i) {
int index = nums[i] > 0 ? nums[i] - 1 : (nums[i] * -1) - 1 ;
if (nums[index] > 0) {
nums[index] *= -1;
}
}
for (auto i = 0 ; i < nums.size() ; ++i) {
if (nums[i] > 0) {
res.push_back(i+1);
}
}
return res;
}
};