पायथन में बिट सरणी का उपयोग करके सरणी के डुप्लिकेट खोजें

मान लीजिए कि हमारे पास 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() । यह स्थिति लेगा

• अनुक्रमणिका :=स्थिति / 2^5

• बिटनो:=पॉज़ और 31

• सही लौटें जब (गिरफ्तारी [इंडेक्स] और (2 ^ बिटनो)) 0 के समान नहीं है

• एक फ़ंक्शन को परिभाषित करें set_val() । यह स्थिति लेगा

• अनुक्रमणिका :=स्थिति / 2^5

• बिटनो:=पॉज़ और 31

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

• मुख्य विधि से, निम्न कार्य करें -

• गिरफ्तार :=bit_arr(320000)

• मेरे लिए 0 से लेकर गिरफ्तारी के आकार तक, करें

  • संख्या:=गिरफ्तार [i]

  • अगर arr.get_val(num) गैर-शून्य है, तो

    • प्रदर्शन संख्या

  • अन्यथा,

  • गिरफ्तारी का set_val(num)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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