刷题

数组中重复的数字

scorlw 发布于

数组中重复的数字

关键词：哈希表

题目描述

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

思路

思路一：哈希表

1.鲁棒性：如果数组的长度小于等于1，返回false

2.利用哈希表的思想将数组的数先存入；

3.再遍历哈希表，返回第一个重复数字。

思路二：

已知数组中的每一个数字值小于数组长度，如果数组中无任何重复的数字，则数组从小到大排序后理应满足第i个位置对应的元素值是i。利用此特性（数组{2, 3, 1, 0, 2, 5, 3}，指针’|’）：

  • |2 3 1 0 2 5 3

指针’|’此时的位置是0，而数组中位置0的元素值是2，2 != 0，将数组中位置0与位置2的元素相互交换。

  • |1 3 2 0 2 5 3

指针’|’的位置依然是0，而数组中位置0的元素值是1，1 != 0，将数组中位置0与位置1的元素相互交换。

  • |3 1 2 0 2 5 3

指针’|’的位置依然是0，而数组中位置0的元素值是3，3 != 0，将数组中位置0与位置3的元素相互交换。

  • |0 1 2 3 2 5 3

指针’|’的位置依然是0，但数组中位置0的元素值是0，0 == 0，将指针’|’右移一位。

  • 0 |1 2 3 2 5 3

指针’|’此时的位置是1，但数组中位置1的元素值是1，1 == 1，将指针’|’右移一位。

  • 0 1 |2 3 2 5 3

指针’|’此时的位置是2，但数组中位置2的元素值是2，2 == 2，将指针’|’右移一位。

  • 0 1 2 |3 2 5 3

指针’|’此时的位置是3，但数组中位置3的元素值是3，3 == 3，将指针’|’右移一位。

  • 0 1 2 3 |2 5 3

指针’|’此时的位置是4，而数组中位置4的元素值是2，2 != 4，且数组中位置4与位置2的元素值相等，那么输出此元素值。

代码

思路一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//此处的代码输入的是数组、数组长度和指向重复数字的指针，返回的是bool表示是否有重复数字
class Solution { 
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length <= 1) return false;
        vector<int> vec(length);
        for(int i = 0; i < length; i++){
            vec[numbers[i]]++;
        }
        for(int i = 0; i < length; i++){
            if(vec[numbers[i]] > 1){
                *duplication = numbers[i];
                return true;
            }
        }
        return false;
    }
};

包含IO的代码：

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
#include <iostream>
#include <vector>

using namespace std;
int findRepeatNumber(vector<int>& nums)
{
    int len = nums.size();
    if(len <= 1)
        return -1;
    vector<int> hush(len);
    for(int i = 0; i < len; i++)
    {
        hush[nums[i]]++;
        if(hush[nums[i]] > 1)
            return nums[i];
    }
    return -1;
}

int main()
{
    int a;
    vector<int> nums;
    while(cin >> a)
    {
        nums.push_back(a);
        if(cin.get() == '\n'){
            break;
        }
    }
    int res = findRepeatNumber(nums);
    cout << res << endl;
    return 0;
}

思路二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//此处的代码输入的是数组、数组长度和指向重复数字的指针，返回的是bool表示是否有重复数字
bool duplicate(int numbers[], int length, int* duplication) {
    if (numbers == 0 || length == 0) {
        return false; // 数组为空或者数组长度是零，即数组中无任何重复数字
    }
    for (int i = 0; i < length; i++) { // 指针初始时是位于数组零位置
        while (numbers[i] != i) { // 当数组中第i位置的元素值不等于i时
            if (numbers[i] == numbers[numbers[i]]) { // 如果数组中第i位置的元素值A等于数组中第A位置的元素值
                *duplication = numbers[i]; // 将此元素值A（数组中第一个重复的元素）记录并返回
                return true;
            }
            else { // 如果数组中第i位置的元素值A不等于数组中第A位置的元素值，则互相交换这两个位置的元素
                int temp = numbers[i]; // 将数组中第i位置的元素值暂存至temp中
                numbers[i] = numbers[temp]; // 将数组中第temp（原第i位置的元素值）位置的元素值赋值于第i位置
                numbers[temp] = temp; // 将temp（原第i位置的元素值）赋值于第temp（原第i位置的元素值）位置
            }
        }
    }
    return false; // 若上述条件均无返回，则直接返回flase（表明数组中并无重复的数字）
}

知识点

1.哈希表思想的应用

2.根据数组的特性解决问题