n개의 요소로 구성된 배열이 있다고 가정합니다. 일부 요소는 두 번 나타나고 다른 요소는 한 번 나타납니다. 요소의 범위는 1 <=A[i] <=n입니다. 배열에 없는 요소를 찾아야 합니다. 제약 조건은 추가 공간을 사용하지 않고 이 문제를 해결해야 하며 시간은 O(n)입니다.
따라서 배열이 [4, 3, 2, 7, 8, 2, 3, 1]이면 결과는 [5, 6]
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n은 배열의 크기입니다.
- 0 ~ n – 1 범위의 i에 대해
- x :=|A[i]| - 1
- A[x]> 0이면 A[x] :=- A[x]
- 배열로 답변 정의
- 0 ~ n – 1 범위의 i에 대해
- A[i]> 0이면 답에 i + 1을 추가합니다.
- 답변
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]";
}
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& v) {
int n = v.size();
for(int i = 0;i < n; i++){
int x = abs(v[i]) - 1;
if(v[x] > 0) v[x] = -v[x];
}
vector <int> ans;
for(int i = 0; i < n; i++){
if(v[i]>0)ans.push_back(i+1);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v{4,3,2,7,8,2,3,5};
print_vector(ob.findDisappearedNumbers(v));
} 입력
[4,3,2,7,8,2,3,5]
출력
[1, 6, ]