পাইথনে বিট অ্যারে ব্যবহার করে অ্যারে-র ডুপ্লিকেট বের করা

ধরা যাক একটি অ্যারে আছে যেখানে nটি আলাদা নম্বর আছে (n সর্বোচ্চ 32,000)। অ্যারেতে ডুপ্লিকেট এন্ট্রি থাকতে পারে এবং আমরা n-এর মান জানি না। যদি আমাদের কাছে শুধু 4 কিলোবাইট মেমরি থাকে, তবে অ্যারে-র সব ডুপ্লিকেট কীভাবে প্রিন্ট করব?

ইনপুট: [2,6,2,11,13,11] → আউটপুট [2,11]।

সমাধানের ধাপসমূহ (বিট অ্যারে / বাইট অ্যারে)

• bit_arr ক্লাস তৈরি করুন:
  • __init__(n): arr = [0] * ((n >> 5) + 1) (প্রতিটি ইন্ট ৩২ বিট)
  • get_val(pos): index = pos >> 5; bitNo = pos & 31; return (arr[index] & (1 << bitNo)) != 0
  • set_val(pos): index = pos >> 5; bitNo = pos & 31; arr[index] |= (1 << bitNo)
• মেইন ফাংশনে: bit_arr(320000) তৈরি করুন, প্রতিটি num-এর জন্য get_val চেক করুন, true হলে প্রিন্ট করুন, false হলে set_val করুন।

উদাহরণ

class bit_arr:
    def __init__(self, n):
        self.arr = [0] * ((n >> 5) + 1)
    def get_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        return (self.arr[self.index] & (1 << self.bitNo)) != 0
    def set_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        self.arr[self.index] |= (1 << self.bitNo)
def is_duplicate(arr):
    ba = bit_arr(320000)
    for i in range(len(arr)):
        num = arr[i]
        if ba.get_val(num):
            print(num, end=" ")
        else:
            ba.set_val(num)
arr = [2, 6, 2, 11, 13, 11]
is_duplicate(arr)

ইনপুট

[2, 6, 2, 11, 13, 11]

আউটপুট

2 11