数组找出重复的数字

发表于 | 更新于: | 分类于 | 热度: ℃
字数统计: 1,486 | 阅读时长 ≈ 7

面试题：找出数组中重复的数字

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

思路：排序一个长度为n的数组需要O(nlogn)的时间，我们选择利用哈希表来解决这个问题。从头到尾顺序扫描数组的每个数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否包含了该数字。如果哈希表没有这个数字，就把它加入哈希表。如果哈希表已经存在该数字，就找到一个重复数字。这个算法的时间复杂度是O(n),他是以创建一个大小O(n)的哈希表为代价。现在我们重排这个数组，从头到尾依次扫描这个数组。当扫描到下标为i的数组时，首先比较这个数字（用m表示）是不是等于i。如果是，则扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果他和地ｍ个数字相等，就找到一个重复的数字；如果他和第m个数字不相等，就把第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
#include <cstdio>
using namespace std;
// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
//        duplication: (输出) 数组中的一个重复的数字
// 返回值:
//        true  - 输入有效，并且数组中存在重复的数字
//        false - 输入无效，或者数组中没有重复的数字
bool duplicate(int numbers[], int length, int* duplication)
{
    if(numbers == nullptr || length<=0)
        return false;
    for(int i=0; i<length; ++i)
    {
        if(numbers[i]<0 || numbers[i]> length-1)
            return false;
    }
     for(int i=0; i<length; ++i)
     {
         while(numbers[i] != i)
         {
             if(numbers[i] == numbers[numbers[i]])
             {
                 *duplication = numbers[i];
                 return true;
             }
             int temp = numbers[i];
             numbers[i] = numbers[temp];
             numbers[temp] = temp;
         }
     }
     return false;
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// ====================测试代码====================
bool contains(int array[], int length, int number)
{
    for(int i = 0; i < length; ++i)
    {
        if(array[i] == number)
            return true;
    }
    return false;
}
void test(char* testName, int numbers[], int lengthNumbers, int expected[], int expectedExpected, bool validArgument)
{
    printf("%s begins: ", testName);
    int duplication;
    bool validInput = duplicate(numbers, lengthNumbers, &duplication);
    if(validArgument == validInput)
    {
        if(validArgument)
        {
            if(contains(expected, expectedExpected, duplication))
                printf("Passed.\n");
            else
                printf("FAILED.\n");
        }
        else
            printf("Passed.\n");
    }
    else
        printf("FAILED.\n");
}
// 重复的数字是数组中最小的数字
void test1()
{
    int numbers[] = { 2, 1, 3, 1, 4 };
    int duplications[] = { 1 };
    test("test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}
// 重复的数字是数组中最大的数字
void test2()
{
    int numbers[] = { 2, 4, 3, 1, 4 };
    int duplications[] = { 4 };
    test("test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}
// 数组中存在多个重复的数字
void test3()
{
    int numbers[] = { 2, 4, 2, 1, 4 };
    int duplications[] = { 2, 4 };
    test("test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}
// 数组中不存在重复的数字
void test4()
{
    int numbers[] = { 0, 1, 2, 3, 4 };
    int duplications[] = { -1 };
    test("test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false);
}
int main()
{
    test1();
    test2();
    test3();
    test4();
    return 0;
}

面试题：不修改数组找出重复的数字

​ 在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

思路：如果没有重复的数字，那么1~n的范围内只有n个数字。有余数组里包含n个数字，所以一定包含了重复的数字。我们把从1~n的数字把中间的数字m分为两部分，前一半为1~m，后一半为m+1~n．如果1~m的数字的数目超过m，那么这一半的区间里一定包含重复数字；否则另外一半m+1~n的区间里一定包含重复的数字。我么可以继续把包含重复的数字的区间一分为二，直到找到一个重复的数字。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
using namespace std;
int countRange(const int* numbers, int length, int start, int end);
// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
// 返回值:
//        正数  - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
//        负数  - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        return -1;
    int start = 1;
    int end = length -1;
    while(start <= end)
    {
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers, length, start, middle);
        if(start == end)
        {
            if(count > 1)
                return start;
            else
                break;
        }
        if((middle-start+1) < count)
        {
            end = middle;
        }
        else
            start = middle+1;
    }
    return -1;
}
int countRange(const int* numbers, int length, int start, int end)
{
    if(numbers == nullptr)
        return 0;
    int count = 0;
    for(int i=0; i<length; i++)
    {
        if(numbers[i]>=start && numbers[i]<=end)
            ++count;
    }
    return count;
}
// ====================测试代码====================
void test(const char* testName, int* numbers, int length, int* duplications, int dupLength)
{
    int result = getDuplication(numbers, length);
    for(int i = 0; i < dupLength; ++i)
    {
        if(result == duplications[i])
        {
            std::cout << testName << " passed." << std::endl;
            return;
        }
    }
    std::cout << testName << " FAILED." << std::endl;
}
// 一个重复的数字
void test1()
{
    int numbers[] = { 3, 2, 1, 4, 4, 5, 6, 7 };
    int duplications[] = { 4 };
    test("test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
// 多个重复的数字
void test2()
{
    int numbers[] = { 2, 3, 5, 4, 3, 2, 6, 7 };
    int duplications[] = { 2, 3 };
    test("test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
// 数组中只有两个数字
void test3()
{
    int numbers[] = { 1, 1 };
    int duplications[] = { 1 };
    test("test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
// 数组中没有重复的数字
void test4()
{
    int numbers[] = { 1, 2, 3, 4, 5 };
    int duplications[] = { 1 };
    test("test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
// 无效的输入
void test5()
{
    int* numbers = nullptr;
    int duplications[] = { 1 };
    test("test5", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
int main()
{
    test1();
    test2();
    test3();
    test4();
    test5();
    return 0;
}
-------------本文结束感谢您的阅读-------------
很有帮助，打赏感谢！
分享到： QQ好友 微信 新浪微博 有道云笔记 豆瓣 收藏夹 复制网址 一键分享 更多
0%