LeetCode – First Duplicate Value

问题：

给定一个整数数组，编写一个函数，返回从左到右读取数组时出现多次的第一个整数。数组元素取值范围是整数1到n， 数组长度为n.

比较特殊情况

[2,3,4,2,3,5] 返回2

[2,3,4,4,2,5] 返回4， 虽然2也是重复数字但是再2之后。

解答：

遍历查找， 两次嵌套循环，同时标注最小索引。

def firstDuplicateValue(array):
    # Write your code here.
    max = len(array)
    value = -1 
    for i in range(len(array)):
        for j in range(len(array)):
            if (j > i and  array[j] == array[i]):
                if (j < max):
                    max = j
                    value = array[i]
    return value

使用哈希表

def firstDuplicateValue(array):
    seen = set()
    for value in array:
        if value in seen:
            return value
        seen.add(value)
    return -1

如果只是找重复的数字不要求是是第一个出现的话，可以用快慢指针， 用于找环的方法。

def firstDuplicateValue(array):
    # Write your code here.
    slow = fast = 0
    while True:
        if slow > len(array)-1 or fast>len(array)-1:
            return -1
        if array[fast] > len(array)-1:
            return -1
        slow = array[slow]
        fast = array[array[fast]]
        if slow == fast:
            break           
    slow = 0
    while slow!=fast:
        slow = array[slow]
        fast = array[fast]
    return slow

修改原数组增加标识

def firstDuplicateValue(array):
    # Write your code here.
    for value in array:
        absvalue = abs(value)
        if array[absvalue - 1] < 0:
            return absvalue
        array[absvalue-1] *= -1;
    return -1

参考及引用

https://www.algoexpert.io/questions/first-duplicate-value

https://leetcode.cn/problems/find-the-duplicate-number/solutions/2361404/287-xun-zhao-zhong-fu-shu-yuan-di-jiao-h-0eja/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

图片from chatgpt