0%

数组中重复的数字

发表于 更新于

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

数字i交换至第i位

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    void swap(int numbers[], const int a, const int b)
    {
        int t = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = t;
    }
    bool duplicate(int numbers[], int length, int* duplication) {
        if (numbers == nullptr || length == 0)
        {
            return false;
        }
        else
        {
            for (int i = 0; i < length; i++)
            {
                while (numbers[i] != i)
                {
                    if (numbers[i] < 0 || numbers[i] >= length)
                    {
                        return false;
                    }
                    else
                    {
                        if (numbers[numbers[i]] == numbers[i])
                        {
                            *duplication = numbers[i];
                            return true;
                        }
                        else
                        {
                            swap(numbers, i, numbers[i]);
                        }
                    }
                }
            }
            return false;
        }
    }
};