資料結構
組建網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的 Set 錯位
假設有一個集合 S，它原本包含從 1 到 n 的數字。但不幸的是，由於某些錯誤，集合中一個數字被複製成集合中的另一個數字，導致一個數字重複，另一個數字丟失。
如果我們有一個數組 nums，表示錯誤發生後此集合的資料狀態。我們的任務是找出出現兩次的數字，再找出丟失的數字。以陣列的形式返回結果。
因此，如果輸入形如 [1,2,3,4,4,6]，則輸出將為 [4,5]
為解決此問題，我們將遵循以下步驟 −
定義一個大小為 2 的陣列 v
s1 := A 中所有數字的和
n := A 的大小
exp_sum := (n * (n + 1))
初始化 i := 0，當 i < n，更新 (將 i 增加 1)，執行 −
如果 A[|A[i]| - 1] > 0，則 −
A[|A[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, ]
更新於: 11-6-2020
217 次瀏覽
廣告