Chương trình tìm phần tử trùng lặp trong danh sách số Python

Cho danh sách nums kích thước n+1 chứa số từ 1 đến n. Theo nguyên lý chim sẻ, chắc chắn có phần tử trùng. Tìm phần tử trùng đó trong O(n) thời gian và không gian O(1).

Ví dụ: nums = [2,1,4,3,5,4] → kết quả 4.

Thuật toán giải quyết (Công thức tổng - O(n) time, O(1) space)

1. Tính tổng mảng: q = sum(nums)
2. n = len(nums) (thực tế là n+1)
3. Tổng lý thuyết 1..n: v = (n-1)*n//2
4. Phần tử trùng = q - v

Lưu ý: phương pháp này chỉ đúng khi có DUY NHẤT một giá trị trùng lặp (có thể lặp nhiều lần).

Ví dụ minh họa

def solve(nums):
    q = sum(nums)
    n = len(nums)
    v = (n - 1) * n // 2
    return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))

Đầu vào

[2,1,4,3,5,4]

Đầu ra

4