python's docs

array 01: fist duplicate


1. 题目

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

  • For a = [2, 3, 3, 1, 5, 2], the output should be
    firstDuplicate(a) = 3.
    There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

  • For a = [2, 4, 3, 5, 1], the output should be
    firstDuplicate(a) = -1.

Input/Output

  • [time limit] 4000ms (py)

  • [input] array.integer a
    Guaranteed constraints:
    1 ≤ a.length ≤ 105,
    1 ≤ a[i] ≤ a.length.

  • [output] integer
    The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

2. 解法

个人解法

def firstDuplicate(a):

    dict = {}
    found = 0

    for i in range(len(a)):
        if a[i] in dict:
            dict[a[i]] += 1
        else:
            dict[a[i]] = 1

        if(dict[a[i]] == 2):
            found = 1
            return a[i]

    if not found:
        return -1

精品解法

def firstDuplicate(A):
    for x in A:
        A[abs(x) - 1] *= -1
        if A[abs(x) - 1] > 0:
            return abs(x)
    return -1

利用了array元素值范围是1到array本身的长度这个条件,每个元素值减一对应array的一个肯定存在的index,轮询array,对每个元素值对应的index初乘以-1,则该值必然为负数,如果检测到该值是正数,说明是元素值第二次存在,则可返回该值。