แนวคิด
เรามีอาร์เรย์ของตัวเลข n โดยที่ n มีค่าสูงสุด 32,000 ตอนนี้อาร์เรย์ที่ระบุอาจมีรายการที่ซ้ำกันและเราไม่รู้ว่า n คืออะไร ตอนนี้เกิดคำถามขึ้นว่าเมื่อมีหน่วยความจำเพียง 4 กิโลไบต์ จะแสดงหรือพิมพ์องค์ประกอบที่ซ้ำกันทั้งหมดในอาร์เรย์ได้อย่างไร
อินพุต
arr[] = {2, 6, 2, 11, 13, 11} ผลลัพธ์
2 11 2 and 11 appear more than once in given array.
อินพุต
arr[] = {60, 50, 60} ผลลัพธ์
60
วิธีการ
ตอนนี้ เรามีหน่วยความจำ 4 กิโลไบต์ ซึ่งระบุว่าเราสามารถระบุได้ถึง 8 * 4 * 210 บิต ควรสังเกตว่า 32 * 210 บิตมีขนาดใหญ่กว่า 32000 ดังนั้นเราจึงสามารถสร้างบิตด้วย 32000 บิต โดยที่แต่ละบิตแทนจำนวนเต็มหนึ่งจำนวน .
อีกครั้งที่ควรสังเกตว่าถ้าเราต้องการสร้างบิตที่มีมากกว่า 32000 บิต เราก็สามารถสร้างได้ง่ายกว่าและมากกว่า 32000; การใช้เวกเตอร์บิตนี้ เราสามารถวนซ้ำผ่านอาร์เรย์ โดยตั้งค่าสถานะแต่ละองค์ประกอบ v โดยการตั้งค่าบิต v เป็น 1 ในกรณีนี้ เมื่อเราสำรวจองค์ประกอบที่ซ้ำกัน เราจะพิมพ์ออกมา
ตัวอย่าง
// C++ program to print all Duplicates in array
#include <bits/stdc++.h>
using namespace std;
// Shows a class to represent an array of bits using
// array of integers
class BitArray{
int *arr1;
public:
BitArray() {}
// Constructor
BitArray(int n1){
// Used to divide by 32. To store n bits, we require
// n/32 + 1 integers (Assuming int is stored
// using 32 bits)
arr1 = new int[(n1 >> 5) + 1];
}
// Now get value of a bit at given position
bool get(int pos1){
// Used to divide by 32 to find position of
// integer.
int index1 = (pos1 >> 5);
// Now determine bit number in arr[index]
int bitNo1 = (pos1 & 0x1F);
// Determine value of given bit number in
// arr1[index1]
return (arr1[index1] & (1 << bitNo1)) != 0;
}
// Used to set a bit at given position
void set(int pos1){
// Determine index of bit position
int index1 = (pos1 >> 5);
// Used to set bit number in arr1[index1]
int bitNo1 = (pos1 & 0x1F);
arr1[index1] |= (1 << bitNo1);
}
//Shows main function to print all Duplicates
void checkDuplicates1(int arr1[], int n1){
// Used to create a bit with 32000 bits
BitArray ba1 = BitArray(320000);
// Used to traverse array elements
for (int i = 0; i < n1; i++){
// Shows index in bit array
int num1 = arr1[i];
// Now if num is already present in bit array
if (ba1.get(num1))
cout << num1 << " ";
// Otherwise or else insert num
else
ba1.set(num1);
}
}
};
// Driver code
int main(){
int arr1[] = {2, 6, 2, 11, 13, 11};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
BitArray obj1 = BitArray();
obj1.checkDuplicates1(arr1, n1);
return 0;
} ผลลัพธ์
2 11
