원래 1에서 n까지의 숫자를 포함하는 집합 S가 있다고 가정합니다. 그러나 불행히도 일부 오류로 인해 집합의 숫자 중 하나가 집합의 다른 숫자와 중복되어 한 숫자가 반복되고 다른 숫자가 손실되었습니다.
이제 오류 후 이 세트의 데이터 상태를 나타내는 nums라는 배열이 있는 경우. 우리의 임무는 두 번 발생하는 숫자를 찾은 다음 놓친 숫자를 찾는 것입니다. 결과를 배열 형태로 반환합니다.
따라서 입력이 [1,2,3,4,4,6]과 같으면 출력은 [4,5]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
크기가 2인 배열 v 정의
-
s1 :=A의 모든 수의 합
-
n :=A의 크기
-
exp_sum :=(n * (n + 1))
-
initialize i :=0의 경우, i
-
만약 A[|A[i]| - 1]> 0, 다음 -
-
아[|아[i]| - 1] =-A[|A[i]| - 1]
-
-
그렇지 않으면
-
v[0] :=|A[i]|
-
루프에서 나오세요
-
-
-
v[1] :=v[0] - (s1 - exp_sum)
-
리턴 v
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findErrorNums(vector<int>& A) {
vector<int> v(2);
long long int s1 = accumulate(A.begin(), A.end(), 0);
int n = A.size();
long long int exp_sum = (n * (n + 1)) / 2;
for (int i = 0; i < n; i++) {
if (A[abs(A[i]) - 1] > 0) {
A[abs(A[i]) - 1] = -A[abs(A[i]) - 1];
}
else {
v[0] = abs(A[i]);
break;
}
}
v[1] = v[0] - (s1 - exp_sum);
return v;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,4,6};
print_vector(ob.findErrorNums(v));
} 입력
{1,2,3,4,4,6} 출력
[4, 5, ]