Hướng dẫn is duplicate allowed in list python? - trùng lặp có được phép trong danh sách python không?

Trong bài viết này, chúng tôi sẽ thảo luận về các cách khác nhau để kiểm tra xem danh sách có chứa bất kỳ yếu tố trùng lặp nào hay không.

Giả sử chúng ta có một danh sách các yếu tố, tức là.

listOfElems = ['Hello', 'Ok', 'is', 'Ok', 'test', 'this', 'is', 'a', 'test']

Bây giờ chúng tôi muốn kiểm tra xem danh sách này có chứa bất kỳ phần tử trùng lặp hay không. Có một số cách để làm điều này, nhưng ở đây chúng tôi sẽ thảo luận về 3 cách và cũng sẽ phân tích hiệu suất.

Kiểm tra các bản sao trong danh sách bằng cách sử dụng tập hợp và bằng cách so sánh kích thước

Để kiểm tra xem danh sách có chứa bất kỳ phần tử trùng lặp nào, hãy làm theo các bước sau không,

1. Thêm nội dung của danh sách trong một bộ.
   • Vì tập hợp chỉ chứa các yếu tố duy nhất, do đó sẽ không có bản sao nào được thêm vào tập hợp.
2. So sánh kích thước của bộ và danh sách.
   • Nếu kích thước của danh sách & bộ bằng nhau thì nó có nghĩa là không có bản sao trong danh sách.
   • Nếu kích thước của danh sách & bộ khác nhau thì điều đó có nghĩa là có, có những bản sao trong danh sách.

Chúng tôi đã tạo ra một hàm tuân theo Algo trên, tức là.

def checkIfDuplicates_1(listOfElems):
    ''' Check if given list contains any duplicates '''
    if len(listOfElems) == len(set(listOfElems)):
        return False
    else:
        return True

Bây giờ, hãy để sử dụng chức năng này để kiểm tra xem danh sách của chúng tôi có chứa bất kỳ bản sao nào hay không.

listOfElems = ['Hello', 'Ok', 'is', 'Ok', 'test', 'this', 'is', 'a', 'test']

result = checkIfDuplicates_1(listOfElems)

if result:
    print('Yes, list contains duplicates')
else:
    print('No duplicates found in list')    

Đầu ra

Yes, list contains duplicates

Phân tích độ phức tạp của giải pháp này.

Quảng cáo

Vì chúng tôi đang tạo một tập hợp từ danh sách, vì vậy độ phức tạp sẽ là n (log (n)). So sánh kích thước là hoạt động O (1). Vì vậy, độ phức tạp của giải pháp này là n (log (n)).n(log(n)). Comparing size is a O(1) operation. So, complexity of this solution is n(log(n)).

Ngay cả trong kịch bản tốt nhất, tức là nếu danh sách chỉ chứa phần tử được nhân đôi, thì độ phức tạp của giải pháp này sẽ là n (log (n)) vì chúng tôi chỉ thêm tất cả các yếu tố từ danh sách này sang danh sách khác.n(log(n)) because we are just adding all the elements from list to set.

Hãy cùng nhìn vào một giải pháp tốt hơn khác,

Kiểm tra các bản sao trong danh sách bằng cách sử dụng Set và tìm kiếm bản sao đầu tiên

Thay vì thêm tất cả các yếu tố danh sách vào tập hợp và sau đó tìm kiếm các bản sao. Chúng ta có thể thêm các phần tử từng một vào danh sách và trong khi thêm kiểm tra xem nó có được nhân đôi hay không, tức là.

def checkIfDuplicates_2(listOfElems):
    ''' Check if given list contains any duplicates '''    
    setOfElems = set()
    for elem in listOfElems:
        if elem in setOfElems:
            return True
        else:
            setOfElems.add(elem)         
    return False

Bây giờ, hãy để sử dụng chức năng này để kiểm tra xem danh sách của chúng tôi có chứa bất kỳ bản sao nào hay không.

listOfElems = ['Hello', 'Ok', 'is', 'Ok', 'test', 'this', 'is', 'a', 'test']

result = checkIfDuplicates_2(listOfElems)

if result:
    print('Yes, list contains duplicates')
else:
    print('No duplicates found in list')    

Đầu ra

Yes, list contains duplicates

Phân tích độ phức tạp của giải pháp này.

Quảng cáoworst case complexity will be n(log(n)).
In best case, we will get to know about duplicate as soon as we encounter it during iteration. So, it will be much lesser than n(log(n)).

Vì chúng tôi đang tạo một tập hợp từ danh sách, vì vậy độ phức tạp sẽ là n (log (n)). So sánh kích thước là hoạt động O (1). Vì vậy, độ phức tạp của giải pháp này là n (log (n)).

Ngay cả trong kịch bản tốt nhất, tức là nếu danh sách chỉ chứa phần tử được nhân đôi, thì độ phức tạp của giải pháp này sẽ là n (log (n)) vì chúng tôi chỉ thêm tất cả các yếu tố từ danh sách này sang danh sách khác.

Hãy cùng nhìn vào một giải pháp tốt hơn khác,

list.count(element)

Kiểm tra các bản sao trong danh sách bằng cách sử dụng Set và tìm kiếm bản sao đầu tiên

Thay vì thêm tất cả các yếu tố danh sách vào tập hợp và sau đó tìm kiếm các bản sao. Chúng ta có thể thêm các phần tử từng một vào danh sách và trong khi thêm kiểm tra xem nó có được nhân đôi hay không, tức là.

def checkIfDuplicates_3(listOfElems):
    ''' Check if given list contains any duplicates '''    
    for elem in listOfElems:
        if listOfElems.count(elem) > 1:
            return True
    return False

Phân tích độ phức tạp của giải pháp này

Trong trường hợp xấu nhất, chúng tôi sẽ thêm tất cả các yếu tố của danh sách trong một tập hợp để thấy rằng danh sách của chúng tôi không chứa bất kỳ bản sao nào. Vì vậy, độ phức tạp trường hợp xấu nhất sẽ là n (log (n)). Trong trường hợp tốt nhất, chúng ta sẽ biết về trùng lặp ngay khi chúng ta gặp nó trong quá trình lặp lại. Vì vậy, nó sẽ ít hơn nhiều so với n (log (n)).

listOfElems = ['Hello', 'Ok', 'is', 'Ok', 'test', 'this', 'is', 'a', 'test']

result = checkIfDuplicates_3(listOfElems)

if result:
    print('Yes, list contains duplicates')
else:
    print('No duplicates found in list')    

Đầu ra

Yes, list contains duplicates

Phân tích độ phức tạp của giải pháp này.
This is the most inefficient solution till now with complexity O(n^2)

Quảng cáo

def checkIfDuplicates_1(listOfElems):
    ''' Check if given list contains any duplicates '''
    if len(listOfElems) == len(set(listOfElems)):
        return False
    else:
        return True

Output:

def checkIfDuplicates_1(listOfElems):
    ''' Check if given list contains any duplicates '''
    if len(listOfElems) == len(set(listOfElems)):
        return False
    else:
        return True