หาค่าซ้ำในอาร์เรย์ด้วยบิตอาร์เรย์ใน C++

แนวคิด

มีอาร์เรย์ n จำนวน โดย n สูงสุด 32,000 อาร์เรย์อาจมีค่าซ้ำ และเราไม่รู้ n จริงๆ คำถามคือ ด้วยหน่วยความจำเพียง 4 กิโลไบต์ จะแสดงค่าซ้ำทั้งหมดในอาร์เรย์อย่างไร?

อินพุต

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

เอาต์พุต

2 11 2 และ 11 ปรากฏมากกว่า 1 ครั้งในอาร์เรย์ที่กำหนด

อินพุต

arr[] = {60, 50, 60}

เอาต์พุต

60

วิธีการ

มีหน่วยความจำ 4 KB หมายถึงสามารถที่อยู่ได้ถึง 8 * 4 * 2^10 บิต หมายเหตุ: 32 * 2^10 บิต มากกว่า 32,000 ดังนั้นสร้างบิตเวกเตอร์ 32,000 บิต โดยแต่ละบิตแทนจำนวนเต็มหนึ่งจำนวน

อีกทั้ง หากต้องการบิตมากกว่า 32,000 บิต สร้างได้ง่ายๆ ด้วยบิตเวกเตอร์นี้ สามารถวนลูปผ่านอาร์เรย์ ทำเครื่องหมายแต่ละสมาชิก v โดยเซตบิต v เป็น 1 เมื่อเจอค่าซ้ำ ให้พิมพ์ออกมา

ตัวอย่างโค้ด C++

// โปรแกรม C++ พิมพ์ค่าซ้ำทั้งหมดในอาร์เรย์
#include <bits/stdc++.h>
using namespace std;

// คลาสแทนอาร์เรย์บิตโดยใช้อาร์เรย์จำนวนเต็ม
class BitArray {
    int *arr1;
public:
    BitArray() {}
    // Constructor
    BitArray(int n1) {
        // หาร 32 เพื่อเก็บ n บิต ต้องใช้ n/32 + 1 จำนวนเต็ม
        // (สมมติ int ใช้ 32 บิต)
        arr1 = new int[(n1 >> 5) + 1];
    }
    // รับค่าบิตที่ตำแหน่งที่กำหนด
    bool get(int pos1) {
        // หาร 32 หาตำแหน่งจำนวนเต็ม
        int index1 = (pos1 >> 5);
        // หาหมายเลขบิตใน arr[index]
        int bitNo1 = (pos1 & 0x1F);
        // ค่าของบิตที่กำหนดใน arr1[index1]
        return (arr1[index1] & (1 << bitNo1)) != 0;
    }
    // เซตบิตที่ตำแหน่งที่กำหนด
    void set(int pos1) {
        // หาดัชนีตำแหน่งบิต
        int index1 = (pos1 >> 5);
        // เซตหมายเลขบิตใน arr1[index1]
        int bitNo1 = (pos1 & 0x1F);
        arr1[index1] |= (1 << bitNo1);
    }
    // ฟังก์ชันหลักพิมพ์ค่าซ้ำทั้งหมด
    void checkDuplicates1(int arr1[], int n1) {
        // สร้างบิตเวกเตอร์ 320,000 บิต
        BitArray ba1 = BitArray(320000);
        // วนลูปสมาชิกอาร์เรย์
        for (int i = 0; i < n1; i++) {
            // ดัชนีในบิตอาร์เรย์
            int num1 = arr1[i];
            // หาก num อยู่ในบิตอาร์เรย์แล้ว
            if (ba1.get(num1))
                cout << num1 << " ";
            // มิฉะนั้น ใส่ num
            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;
}

เอาต์พุต

2 11