सरणी / पूर्णांक की सूची में डुप्लीकेट खोजें - पायथन, सरणी, एल्गोरिदम, सूची, सॉर्टिंग

एक दिया गया array/list का integers, डुप्लिकेट आउटपुट।

इसके अलावा, मैं वास्तव में क्या देख रहा हूं: क्या समाधानों में सबसे अच्छा समय है? सर्वश्रेष्ठ अंतरिक्ष प्रदर्शन? क्या सर्वश्रेष्ठ समय और सर्वश्रेष्ठ अंतरिक्ष प्रदर्शन दोनों करना संभव है? बस उत्सुक। धन्यवाद!

उदाहरण के लिए: सूची दी गई [4,1,7,9,4,5,2,7,6,5,3,6,7]जवाब होगा [4,7,6,5] (आउटपुट का क्रम कोई फर्क नहीं पड़ता)।

में अपना समाधान लिखा python.

यहाँ एक समाधान मैंने हैश और बाइनरी खोज का उपयोग करके लिखा है।

def binarySearch(array, number):
start = 0
end = len(array)
mid = (end + start) // 2
while (end > start):
mid = start + (end - start) // 2
if array[mid] == number:
return (mid, True)
elif number > array[mid]:
if start == mid:
return (mid + 1, False)
start = mid
else:
end = mid

return (mid, False)

def findDuplicatesWithHash(array):
duplicatesHash = {}
duplicates = []
for number in array:
try:
index,found = binarySearch(duplicates, number)
if duplicatesHash[number] == 0 and not found:
duplicates.insert(index, number)
except KeyError as error:
duplicatesHash[number] = 0

duplicatesSorted = sorted(duplicates, key=lambda tup: tup)
return duplicatesSorted

उत्तर:

डुप्लिकेट प्राप्त करने का एक तरीका:

l = [4,1,7,9,4,5,2,7,6,5,3,6]
import collections

print([item for item, count in collections.Counter(l).items() if count > 1])

डुप्लिकेट ढूँढना छँटाई के समान है। यानी, डुप्लिकेट होने पर खोजने के लिए प्रत्येक तत्व को अन्य सभी तत्वों की तुलना में प्रत्यक्ष या अप्रत्यक्ष रूप से होना चाहिए। एक एस्कॉर्ट को आउटपुट तत्वों में संशोधित कर सकता है जिनमें ओ (एन) स्पेसियल जटिलता और ओ (एन * लॉग (एन)) औसत समय जटिलता के साथ एक आसन्न मिलान तत्व है।

डुप्लिकेट खोजने के लिए कई समाधान हैं। यह प्रश्न पूरी तरह से सामान्य है, कोई भी यह मान सकता है कि इसकी सूची दी गई है n मान, डुप्लिकेट की संख्या सीमा में है [0, n/2].

आप किन संभावित तरीकों के बारे में सोच सकते हैं?

1. हैश टेबल दृष्टिकोण:

   मान को सूची में ट्रेस करते समय स्टोर करें यदि हैश तालिका में मान पहले से मौजूद नहीं है। यदि मान मौजूद है, तो आपके पास डुप्लिकेट है।

   Algorithm FindDuplicates(list)
   hash_table <- HashTable()
   duplicates <- List()
   for value in list:
   if value in hash_table:
   duplicates.add(value)
   else:
   hash_table.add(value, true)
   

   • पहर: O(n) सभी मूल्यों के माध्यम से पार करने के लिए
   • अंतरिक्ष: O(n) हैश तालिका में सभी संभावित मूल्यों को बचाने के लिए।

2. क्रमबद्ध करें

   सरणी को क्रमबद्ध करें और पड़ोसी मानों को पार करें।

   Algorithm FindDuplicates(list)
   list.sort()
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if list[i] = list[i-1]:
   duplicates.add(list[i])
   

   • पहर: O(n.logn) + O(n) = O(n.logn) सभी मानों को क्रमबद्ध और क्रमबद्ध करना
   • अंतरिक्ष: O(1) डुप्लिकेट बनाने के लिए कोई अतिरिक्त स्थान नहीं बनाया गया

3. हर मूल्य के लिए जाँच करें

   प्रत्येक मान के लिए जाँचें कि क्या मान सरणी में मौजूद है।

   Algorithm Search(i, list):
   for j <- [0, len(list)-1] - [i]:
   if list[j] = list[i]:
   return true
   return false
   
   Algorithm FindDuplicates(list)
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if Search(i, list):
   duplicates.add(list[i])
   

   पहर: O(n^2) तुलना की संख्या है n*n(-1) अंतरिक्ष: O(1) डुप्लिकेट बनाने के लिए कोई अतिरिक्त स्थान नहीं बनाया गया

नोट: डुप्लिकेट सरणी के लिए स्थान को अंतरिक्ष जटिलता समीकरणों में शामिल नहीं किया जा सकता है क्योंकि यह वह परिणाम है जो हम चाहते हैं।

क्या आप कुछ और सोच सकते हैं?