Đặt Không phù hợp trong C ++

Giả sử có một tập S ban đầu chứa các số từ 1 đến n. Nhưng thật không may, do một số lỗi, một trong các số trong tập hợp đã bị trùng lặp thành một số khác trong tập hợp, dẫn đến việc lặp lại một số và mất một số khác.

Bây giờ nếu chúng ta có một mảng được gọi là nums đang đại diện cho trạng thái dữ liệu của tập hợp này sau lỗi. Nhiệm vụ của chúng ta là tìm số xuất hiện hai lần và sau đó tìm số bị thiếu. trả về kết quả ở dạng mảng.

Vì vậy, nếu đầu vào là [1,2,3,4,4,6], thì đầu ra sẽ là [4,5]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng v có kích thước 2

• s1:=tổng của tất cả các số của A

• n:=kích thước của A

• exp_sum:=(n * (n + 1))

• để khởi tạo i:=0, khi i

  • nếu A [| A [i] | - 1]> 0, sau đó -

    • A [| A [i] | - 1] =-A [| A [i] | - 1]

  • Nếu không

    • v [0]:=| A [i] |

    • Ra khỏi vòng lặp

• v [1]:=v [0] - (s1 - exp_sum)

• trở lại v

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{1,2,3,4,4,6}

Đầu ra

[4, 5, ]