Wie finde ich die Duplikate in einer Liste und erstelle eine weitere Liste mit ihnen?

Question

Wie finde ich die Duplikate in einer Liste mit ganzen Zahlen und erstelle eine weitere Liste mit den Duplikaten?

Answer 1

Um dieses Problem zu lösen, können wir mehrere verschiedene Methoden anwenden. Diese beiden sind gängige Lösungen, aber bei der Umsetzung in realen Szenarien müssen wir auch die Zeitkomplexität berücksichtigen.

import random
import time

dupl_list = [random.randint(1,1000) for x in range(500)]
print("List with duplicate integers")
print (dupl_list)

#Method 1 
print("******************Method 1 *************")

def Repeat_num(x):
    _size = len(x)
    repeated = []
    for i in range(_size):
        # print(i)
        k = i + 1
        for j in range(k, _size):
            # print(j)
            if x[i] == x[j] and x[i] not in repeated:
                repeated.append(x[i])
    return repeated

start = time.time()
print(Repeat_num(dupl_list))
end = time.time()
print("The time of execution of above program is :",(end-start) * 10**3, "ms")

print("***************Method 2****************")

#method 2 - using count()
def repeast_count(dup_list):
  new = []
  for a in dup_list:
      # print(a)
      # checking the occurrence of elements
      n = dup_list.count(a)
      # if the occurrence is more than
      # one we add it to the output list
      if n > 1:
          if new.count(a) == 0:  # condition to check
              new.append(a)
  return new

start = time.time()
print(repeast_count(dupl_list))
end = time.time()
print("The time of execution of above program is :",(end-start) * 10**3, "ms")

Musterausgabe::

List with duplicate integers
[5, 45, 28, 81, 32, 98, 8, 83, 47, 95, 41, 49, 4, 1, 85, 26, 38, 82, 54, 11]
******************Method 1 *************
[]
The time of execution of above program is : 1.1069774627685547 ms
***************Method 2****************
[]
The time of execution of above program is : 0.1881122589111328 ms

Für das allgemeine Verständnis ist Methode 1 gut, aber für die tatsächliche Umsetzung ziehe ich Methode 2 vor, da sie weniger Zeit benötigt als Methode 1.

Answer 2

Ich habe festgestellt, dass die meisten Lösungen eine Komplexität von O(n * n) haben und bei großen Listen sehr langsam sind. Deshalb wollte ich die Funktion, die ich geschrieben habe und die ganze Zahlen oder Zeichenketten unterstützt und im besten Fall O(n) ist, mit Ihnen teilen. Für eine Liste mit 100k Elementen benötigte die beste Lösung über 30s, während meine in .12s fertig ist.

def get_duplicates(list1):
    '''Return all duplicates given a list. O(n) complexity for best case scenario.
    input: [1, 1, 1, 2, 3, 4, 4]
    output: [1, 1, 4]
    '''
    dic = {}
    for el in list1:
        try:
            dic[el] += 1
        except:
            dic[el] = 1
    dupes = []
    for key in dic.keys():
        for i in range(dic[key] - 1):
            dupes.append(key)
    return dupes

list1 = [1, 1, 1, 2, 3, 4, 4]
> print(get_duplicates(list1))
[1, 1, 4]

Oder um einzigartige Duplikate zu erhalten:

> print(list(set(get_duplicates(list1))))
[1, 4]

Answer 3

Nehmen wir also an, wir haben diese Liste von Elementen:

a = [1, 2, 3, 2, 1, 5, 6, 5, 5, 5]

Wir können nur mit Mengen arbeiten, um die einzigartige Elemente :

unique = set()
for num in a:
    if num not in unique:
        unique.add(num)
    else:
        unique = unique - set([num])

und schließlich:

>>> unique
{3, 6}

Wenn Sie die Duplikate erhalten möchten, können Sie dies einfach tun:

>>> duplicates = set(a) - unique
>>> duplicates
{1, 2, 5}

Anmerkungen:

• Das Nachschlagen von Elementen in Mengen ist O(1)
• Das Entfernen von Elementen aus Mengen ist O(1)

Answer 4

list2 = [1, 2, 3, 4, 1, 2, 3]
lset = set()
[(lset.add(item), list2.append(item))
 for item in list2 if item not in lset]
print list(lset)

Answer 5

Versuchen Sie dies Für die Überprüfung von Duplikaten

>>> def checkDuplicate(List):
    duplicate={}
    for i in List:
            ## checking whether the item is already present in dictionary or not
            ## increasing count if present
            ## initializing count to 1 if not present

        duplicate[i]=duplicate.get(i,0)+1

    return [k for k,v in duplicate.items() if v>1]

>>> checkDuplicate([1,2,3,"s",1,2,3])
[1, 2, 3]