Tìm số trùng lặp trong mảng (Find the Duplicate Number) trong Python

Giả sử chúng ta có mảng nums chứa n + 1 số nguyên. Các phần tử nằm trong khoảng 1 đến n. Chứng minh rằng ít nhất một số trùng lặp phải tồn tại. Giả sử chỉ có một số trùng lặp, chúng ta phải tìm số đó. Ví dụ, nếu mảng là [1,3,4,2,2], số trùng lặp sẽ là 2.

Để giải quyết, chúng ta sử dụng thuật toán Floyd's Tortoise and Hare (chuột và thỏ):

• Khởi tạo tho = nums[0] và ruot = nums[0].

• Lặp vô hạn:

  • tho = nums[nums[tho]] (nhảy 2 bước).
  • ruot = nums[ruot] (nhảy 1 bước).
  • Nếu tho == ruot, thoát vòng lặp.

• Khởi tạo con_tro = nums[0].

• Khi con_tro khác ruot:

  • con_tro = nums[con_tro].
  • ruot = nums[ruot].

• Trả về con_tro.

Ví dụ

class Solution(object):
    def findDuplicate(self, nums):
        tho = nums[0]
        ruot = nums[0]
        while True:
            tho = nums[nums[tho]]
            ruot = nums[ruot]
            if tho == ruot:
                break
        con_tro = nums[0]
        while con_tro != ruot:
            con_tro = nums[con_tro]
            ruot = nums[ruot]
        return con_tro

ob1 = Solution()
print(ob1.findDuplicate([3,1,3,4,2]))

Đầu vào

[3,1,3,4,2]

Đầu ra

3