#This is a slow version of finding duplicates, it runs in O(N^2) def findDuplicateSlow(inputArray): for value1 in range(0, len(inputArray) - 1): for value2 in range(value1 + 1, len(inputArray)): if inputArray[value1] == inputArray[value2]: return inputArray[value1] return -1 #Finds the first duplicate in an unsorted array in linear time def findDuplicate(inputArray): #Setup a dictionary/set of values that have been seen seenValues = {} for value in inputArray: #If a value has not been seen, add it to the set of seen values if not value in seenValues: #Add the value to the dictionary seenValues[value] = True else: #This else condition means the value has been seen before #so it must be a duplicate return value #If there are no duplicates, return -1 return -1 arr = [0,5,6,7,3,4,8,9,1,6,2] #findDuplicateSlow(arr) findDuplicate(arr)
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question