สมมติว่าเรามีอาร์เรย์ของตัวเลข N โดยที่แต่ละองค์ประกอบในอาร์เรย์มีจำนวนครั้งเท่ากัน (m ครั้ง ซึ่งจะได้รับด้วย) ยกเว้นองค์ประกอบเดียว เราต้องหาองค์ประกอบนี้
ดังนั้น หากอินพุตเป็น A =[6, 2, 7, 2, 2, 6, 6], m =3 ผลลัพธ์จะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
INT_SIZE :=8 * ขนาดของตัวแปรประเภทจำนวนเต็ม
-
กำหนดจำนวนอาร์เรย์ของขนาด - INT_SIZE และเติม 0
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
ถ้า (arr[j] AND 2^i) ไม่เท่ากับ 0 แล้ว −
-
นับ[i] :=นับ[i] + 1
-
-
res :=0
-
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
res :=res + ((นับ[i] mod m) * 2^i)
-
-
ผลตอบแทน
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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);
} อินพุต
{ 6, 2, 5, 2, 2, 6, 6 } ผลลัพธ์
5
