मान लीजिए हमारे पास 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 लेगा
index := pos / 2^5
bitNo := pos AND 31
true वापस करें जब (arr[index] AND (2^bitNo)) 0 के समान नहीं है
एक फ़ंक्शन set_val() परिभाषित करें। यह pos लेगा
index := pos / 2^5
bitNo := pos AND 31
arr[index] := arr[index] OR (2^bitNo)
मुख्य विधि से, निम्नलिखित करें -
arr := bit_arr(320000)
i के लिए 0 से arr के आकार की सीमा में, करें
num := arr[i]
यदि arr.get_val(num) शून्येतर है, तो
num प्रदर्शित करें
अन्यथा,
arr का 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
