问题陈述

Problem Statement:

You have been given an array of length = n. The array contains integers from 0 to n - 2. Each number in the array is present exactly once except for one number which is present twice. Find and return this duplicate number present in the array

Example: * arr = [0, 2, 3, 1, 4, 5, 3] * output = 3 (because 3 is present twice)

The expected time complexity for this problem is O(n) and the expected space-complexity is O(1).

python实现

1
2
3
4
5
6
7
8
9
10
def duplicate_number(arr):
    if arr is None:
        return None
    summary = 0
    sum_arr = 0
    for i in range(len(arr)):
        if i < len(arr)-1:
            summary += i
        sum_arr += arr[i]
    return sum_arr - summary

测试用例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def test_function(test_case):
    arr = test_case[0]
    solution = test_case[1]
    output = duplicate_number(arr)
    if output == solution:
        print("Pass")
    else:
        print("Fail")

arr = [0, 0]
solution = 0

test_case = [arr, solution]
test_function(test_case)

arr = [0, 2, 3, 1, 4, 5, 3]
solution = 3

test_case = [arr, solution]
test_function(test_case)

arr = [0, 1, 5, 4, 3, 2, 0]
solution = 0

test_case = [arr, solution]
test_function(test_case)

arr = [0, 1, 5, 5, 3, 2, 4]
solution = 5

test_case = [arr, solution]
test_function(test_case)