Tìm phần tử có tần số khác với các phần tử mảng khác trong C ++

Giả sử chúng ta có một mảng gồm N số, trong đó mỗi phần tử trong mảng xuất hiện cùng một số lần (m lần, giá trị này cũng cho trước) ngoại trừ một phần tử, Chúng ta phải tìm phần tử này.

Vì vậy, nếu đầu vào là A =[6, 2, 7, 2, 2, 6, 6], m =3, thì đầu ra sẽ là 7.

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

• INT_SIZE:=8 * kích thước của một biến kiểu số nguyên

• Xác định kích thước số mảng - INT_SIZE. và điền bằng 0

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

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

    • nếu (arr [j] AND 2 ^ i) không bằng 0, thì -

      • count [i]:=count [i] + 1

    • res:=0

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

    • res:=res + ((count [i] mod m) * 2 ^ i)

  • trả lại res

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;
int selectUnique(unsigned int arr[], int size, int m){
   int INT_SIZE = 8 * sizeof(unsigned int);
   int count[INT_SIZE];
   memset(count, 0, sizeof(count));
   for(int i = 0; i < INT_SIZE; i++)
      for(int j = 0; j < size; j++)
         if((arr[j] & (1 << i)) != 0)
            count[i] += 1;
   unsigned res = 0;
   for(int i = 0; i < INT_SIZE; i++)
      res += (count[i] % m) * (1 << i);
   return res;
}
main(){
   unsigned int arr[] = { 6, 2, 5, 2, 2, 6, 6 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int m = 3;
   cout << selectUnique(arr, size, m);
}

Đầu vào

{ 6, 2, 5, 2, 2, 6, 6 }

Đầu ra

5