i want to find out the index of the elements in an array of duplicate elements
Multi tool use
Clash Royale CLAN TAG#URR8PPPi want to find out the index of the elements in an array of duplicate elements
a=[2, 1, 3, 5, 3, 2]
def firstDuplicate(a):
for i in range(0,len(a)):
for j in range(i+1,len(a)):
while a[i]==a[j]:
num=[j]
break
print(num)
print(firstDuplicate(a))
The output should be coming as 4 and 5 but it's coming as 4 only
You duplicates are at indices 4 & 5. And your print needs to be inside the outer loop. And the
while doesn't make sense.– PM 2Ring
yesterday
while
2 Answers
2
You can find the indices of all duplicates in an array in O(n) time and O(1) extra space with something like the following:
def get_duplicate_indices(arr):
inds =
for i, val in enumerate(arr):
val = abs(val)
if arr[val] >= 0:
arr[val] = -arr[val]
else:
inds.append(i)
return inds
get_duplicate_indices(a)
[4, 5]
Note that this will modify the array in place! If you want to keep your input array un-modified, replace the first few lines in the above with:
def get_duplicate_indices(a):
arr = a.copy() # so we don't modify in place. Drawback is it's not O(n) extra space
inds =
for i, val in enumerate(a):
# ...
Essentially this uses the sign of each element in the array as an indicator of whether a number has been seen before. If we come across a negative value, it means the number we reached has been seen before, so we append the number's index to our list of already-seen indices.
Note that this can run into trouble if the values in the array are larger than the length of the array, but in this case we just extend the working array to be the same length as whatever the maximum value is in the input. Easy peasy.
Cute, but impractical if the list integers are scattered over a large range, and not much use for non-integer lists. But why do you compute
abs(arr[i]) 3 times?– PM 2Ring
yesterday
abs(arr[i])
@PM2Ring I figured any improvement in performance gained by storing the value is going to be super minimal, and I thought it was clearer this way. And yes, you could run into some memory issues if your integers are very large, but I thought it was a neat solution. No good for non-integer arrays, you are correct.
– Engineero
yesterday
Sure, getitem & abs are pretty cheap, but a local lookup is very fast. And you are doing it in a loop... IMHO, the repetition actually makes the code harder to read since you need to look closely to verify that it is exact repetition.
– PM 2Ring
yesterday
@PM2Ring good point. I updated it to store the absolute value, and to use
enumerate to iterate over the indices and values instead of a range with lookup. Hopefully clearer that way.– Engineero
yesterday
enumerate
Definitely much clearer to me.
– PM 2Ring
yesterday
There are some things wrong with your code. The following will collect the indexes of every first duplicate:
def firstDuplicate(a):
num = # list to collect indexes of first dupes
for i in range(len(a)-1): # second to last is enough here
for j in range(i+1, len(a)):
if a[i]==a[j]: # while-loop made little sense
num.append(j) # grow list and do not override it
break # stop inner loop after first duplicate
print(num)
There are of course more performant algorithms to achieve this that are not quadratic.
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Why do you expect 4 and 3?
– schwobaseggl
yesterday