CODEWITHSUNDEEP
python-3.xalgorithmduplicates
KvothesLute
KvothesLute

Reputation: 195

Algorithm for calculating the duplicates in a list

The code below prints out the numbers which are duplicated in A. From my understanding, the for loop goes through each element in the list and turns it into a negative number, though i can not figure out why it does not turn the numbers it prints (which are at at position 0,4,5) negative.

A = [1,2,3,1,3,6,6]
def printRepeating(arr, size): 

    print("The repeating elements are: ") 

    for i,x in enumerate(arr): 

        if arr[abs(arr[i])] >= 0: 

            arr[abs(arr[i])] = -arr[abs(arr[i])] 
            print(arr)
        else: 
            print (abs(arr[i]), end = " ") 
printRepeating(A,len(A))

Upvotes: 1

Views: 270

Answers (4)

Ashok KS
Ashok KS

Reputation: 691

The below code can be used to find repeated elements in the list and also unique elements in the list.

from collections import Counter
A = [1,2,3,1,3,6,6]

B =  Counter(A)

The below line prints repeated elements.

[k for k, v in B.items() if v > 1]
Output : [1, 3, 6]

The below line prints unique elements.

[k for k, v in B.items() if v == 1]
Output : [2]

Upvotes: 0

Nico Schertler
Nico Schertler

Reputation: 32597

The algorithm assumes that all entries are strictly positive and smaller than the length of the list. Then, what it does is essentially using the sign of the i-th element to store if it already saw number i. In your example:

A=[1,2,3,1,3,6,6]  Take 1
A[1] is positive, i.e. we have not seen it. Make it negative to mark it
A=[1,-2,3,1,3,6,6] Take -2  (stands for 2)
A[2] is positive, i.e. we have not seen it. Make it negative to mark it
A=[1,-2,-3,1,3,6,6] Take -3
A[3] is positive, i.e. we have not seen it. Make it negative to mark it
A=[1,-2,-3,-1,3,6,6] Take -1
A[1] is negative, i.e. we have already seen it. Report it.
A=[1,-2,-3,-1,3,6,6] Take 3
A[3] is negative, i.e. we have already seen it. Report it.
...

Upvotes: 1

user3386109
user3386109

Reputation: 34829

The algorithm assumes:

  1. all the elements of the array start as positive numbers, and
  2. all the elements of the array are less than the length of the array.

In your example, since the length of the array is 7, all the elements in the array must be between 1 and 6.

What the algorithm does is change array[k] to negative to indicate that k has been seen. For example, since 1 is the first number seen, array[1] is changed to a negative number. The next time 1 is seen, array[1] is already negative, so 1 must be a duplicate.

Upvotes: 1

James Riley
James Riley

Reputation: 26

If you just want to print the repeated values in the list then why not try this:

A = [1, 2, 3, 1, 3, 6, 6]
def get_repeated_elements(lst):
   return list(set((i for i in lst if lst.count(i) > 1)))
print(get_repeated_elements(A))

This function converts the passed array into a generator of duplicated values and then converts this into a set to filter out duplicates in the generator and then converts this into a list for returning to the caller. This is a far shorter function than the one given.

Upvotes: 1

Related Questions