Tìm các phần tử trùng lặp trong mảng bằng mảng bit trong C++

Khái niệm

Cho mảng n số, n tối đa 32.000. Mảng có thể chứa phần tử trùng lặp và ta không biết n chính xác. Với chỉ 4 Kilobyte bộ nhớ, làm thế nào để in tất cả phần tử trùng lặp?

Đầu vào

arr[] = {2, 6, 2, 11, 13, 11}

Đầu ra

2 11

2 và 11 xuất hiện nhiều hơn một lần.

Đầu vào

arr[] = {60, 50, 60}

Đầu ra

60

Phương pháp

4 Kilobyte = 8 * 4 * 2^10 bit. 32 * 2^10 bit > 32000. Ta tạo mảng bit 32000 bit, mỗi bit đại diện cho một số nguyên. Dùng vector bit này để duyệt mảng, đánh dấu bit v = 1 cho mỗi phần tử v. Khi gặp phần tử trùng lặp (bit đã là 1), in ra.

Ví dụ

// Chương trình C++ in tất cả phần tử trùng lặp trong mảng
#include <bits/stdc++.h>
using namespace std;

class BitArray{
    int *arr1;
public:
    BitArray() {}
    BitArray(int n1){
        arr1 = new int[(n1 >> 5) + 1];
    }
    bool get(int pos1){
        int index1 = (pos1 >> 5);
        int bitNo1 = (pos1 & 0x1F);
        return (arr1[index1] & (1 << bitNo1)) != 0;
    }
    void set(int pos1){
        int index1 = (pos1 >> 5);
        int bitNo1 = (pos1 & 0x1F);
        arr1[index1] |= (1 << bitNo1);
    }
    void checkDuplicates1(int arr1[], int n1){
        BitArray ba1 = BitArray(320000);
        for (int i = 0; i < n1; i++){
            int num1 = arr1[i];
            if (ba1.get(num1))
                cout << num1 << " ";
            else
                ba1.set(num1);
        }
    }
};

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

Đầu ra

2 11