C语言数组中重复的数字分析及方法

问题描述

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

思路分析

方法1：暴力遍历

最简单的方法是使用两个循环，从头到尾依次比较每个数字是否重复，时间复杂度为O(n^2)。

方法2：哈希表

哈希表可以将查找时间降到O(1)，开辟一个长度为n的数组，将每个数字记录在对应的数组位置上，如果发现有重复的数字，则直接返回。但需要额外的辅助数组空间，空间复杂度为O(n)。

方法3：原地置换

根据题目数据范围，可以将数组中的数字看做是索引，其下标为值，如果不存在重复，那么只要对数组进行排序，每个数字肯定会在其对应的位置上。因此，可以通过不停的交换数字，使数字归位，如果发现有重复，直接返回。由于操作是原地进行的，所以空间复杂度为O(1)。

代码实现

方法1：暴力遍历

int findRepeatNumber(int* nums, int numsSize){
    for(int i=0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
            if(nums[i]==nums[j]){
                return nums[i];
            }
        }
    }
    return -1;
}

方法2：哈希表

int findRepeatNumber(int* nums, int numsSize){
    int *hash = (int*)malloc(numsSize * sizeof(int)); //开辟哈希表
    memset(hash, 0, sizeof(hash)); //初始化数组为0
    for(int i=0;i<numsSize;i++){
        if(hash[nums[i]]){
            return nums[i];
        }else{
            hash[nums[i]] = 1; //标记出现过的数字
        }
    }
    free(hash); //释放内存
    return -1;
}

方法3：原地置换

int findRepeatNumber(int* nums, int numsSize){
    for(int i=0;i<numsSize;i++){
        while(nums[i]!=i){
            if(nums[i]==nums[nums[i]]){
                return nums[i];
            }
            int tmp = nums[i]; //交换数字
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
    }
    return -1;
}

示例说明

示例1

输入: [2, 3, 1, 0, 2, 5, 3]

输出: 2 或 3

解释：输入的数组中，2和3重复出现了，因此输出2或3都是合法的结果。

示例2

输入: [4, 2, 3, 1, 0]

输出: -1

解释：输入的数组中，不包含重复的数字，因此输出-1。

总结

以上三种方法均可用来解决此问题，方法1最为简单，但时间复杂度较高，在数据规模较大时表现不佳；方法2使用了额外的哈希表空间，但只需要一次遍历即可解决问题；方法3虽然不需要额外空间，但需要进行多次交换，时间复杂度也较高。在实际应用中，需要根据具体情况选择合适的方法。