# LeetCode - First Duplicate Value
Date: 2024-03-18


#### **问题：**

给定一个整数数组，编写一个函数，返回从左到右读取数组时出现多次的第一个整数。数组元素取值范围是整数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