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

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

সুতরাং, যদি ইনপুটটি [2, 6, 2, 11, 13, 11] এর মত হয়, তাহলে আউটপুট হবে [2,11] কারণ প্রদত্ত অ্যারেতে 2 এবং 11 একাধিকবার প্রদর্শিত হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি বাইট-অ্যারে টাইপ ডেটা স্ট্রাকচার bit_arr তৈরি করুন, এতে নিম্নলিখিত পদ্ধতি রয়েছে

• কনস্ট্রাক্টর সংজ্ঞায়িত করুন এটি n

  নেবে

• arr :=আকারের একটি অ্যারে (n / 2^5) + 1, 0 দিয়ে পূরণ করুন

• একটি ফাংশন get_val() সংজ্ঞায়িত করুন। এটি পজিস লাগবে

• সূচক :=pos / 2^5

• bitNo :=pos AND 31

• সত্য ফেরত দিন যখন (arr[index] AND (2^bitNo)) 0 এর মত না হয়

• একটি ফাংশন সেট_ভাল() সংজ্ঞায়িত করুন। এটি পজিস লাগবে

• সূচক :=pos / 2^5

• bitNo :=pos AND 31

• arr[index] :=arr[index] OR (2^bitNo)

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• arr :=bit_arr(320000)

• আমি 0 থেকে arr এর আকারের মধ্যে, কর

  • সংখ্যা :=arr[i]

  • যদি arr.get_val(num) অ-শূন্য হয়, তাহলে

    • প্রদর্শন সংখ্যা

  • অন্যথায়,

  • সেট_ভাল(সংখ্যা) এর arr

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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):
   arr = bit_arr(320000)
   for i in range(len(arr)):
      num = arr[i]
      if arr.get_val(num):
         print(num, end = " ")
      else:
         arr.set_val(num)
arr = [2, 6, 2, 11, 13, 11]
is_duplicate(arr)

ইনপুট

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

আউটপুট

2 11