寻找重复数287-力扣（数组+【快排|哈希|二分】+c）

傷城~ 2023-01-19 03:28 115阅读 0赞

题目描述  
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

示例 1：

输入：nums = \[1,3,4,2,2\]  
输出：2  
示例 2：

输入：nums = \[3,1,3,4,2\]  
输出：3  
示例 3：

输入：nums = \[1,1\]  
输出：1  
示例 4：

输入：nums = \[1,1,2\]  
输出：1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-the-duplicate-number  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解  
分析：这道题目解法有很多，自己实现了几种，如下：  
第一种思路：快排+比较，排序后只要判断相邻两个元素是否相等，就可以了。时间复杂度O(NlogN)，空间复杂度O(1)

第二种思路：使用哈希表，只要出现重复的，就返回该结果就可以了。时间复杂度O(NlogN)，空间复杂度O(N)

第三种思路：二分查找，对于该题，有个条件：**其数字都在 1 到 n 之间**，因此对于某个范围内的数，可以运用二分法确定，二分的思路：  
先猜一个数（有效范围 \[left, right\]里的中间数 mid），然后统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 大于 mid，重复元素就在区间 \[left, mid\] 里，否则重复的元素就在区间\[mid,right\]里。

时间复杂度：O(nlogn)，其中 n 为nums 数组的长度。二分查找最多需要二分 O(logn) 次，每次判断的时候需要O(n)遍历数组求解小于等于mid 的数的个数，因此总时间复杂度为O(nlogn)。  
空间复杂度：O(1)。我们只需要常数空间存放若干变量。

例如对于nums = \[1,3,4,2,2\]

*  left = 1，right=5-1，mid=(left + right)/2=2，小于等于2的元素有1，2，2，故cnt=3，3>mid，所以重复元素在\[left，mid\]里，此时令right=mid-1
 *  left=1，right=1，mid=(1+1)/2=1，此时小于等于1的元素有1，cnt=1，1=mid，所以重复元素在\[mid+1, right\]里面，令left=mid+1
 *  left=2，right=1，此时终止即可，寻找的重复数据即是left=2

代码：

第一种思路：

int cmp(const void* a, const void* b)
    { 
        return *(int *)b - *(int *)a;
    }
    int findDuplicate(int* nums, int numsSize){ 
        qsort(nums, numsSize,  sizeof(int), cmp);
        int res = 0;
        for(int i=0; i<numsSize; i++)
        { 
            if(nums[i] == nums[i+1])
            { 
                res = nums[i];
                break;
            }
        }
        return res;
    
    }

第二种思路：

struct hashTable{ 
        int key;
        UT_hash_handle hh;
    };
    
    int findDuplicate(int* nums, int numsSize){ 
        int res = 0;
        struct hashTable *set = NULL;
        for(int i = 0; i < numsSize; i++)
        { 
            struct hashTable *tmp;
            HASH_FIND_INT(set, &nums[i], tmp);
            if(tmp == NULL)
            { 
                tmp = (struct hashTable *)malloc(sizeof(struct hashTable));
                tmp->key = nums[i];
                HASH_ADD_INT(set, key, tmp);
            }
            else
            { 
                res = nums[i];
                break;
            }
        }
        return res;
    }

第三种思路：

int findDuplicate(int* nums, int numsSize){ 
        int left = 1;
        int right = numsSize - 1;
        while(left <= right)
        { 
            int mid = left + (right - left)/2;
            int cnt = 0;
            for(int i = 0; i < numsSize; i++)
            { 
                if(nums[i] <= mid) cnt++;
            }
            if(cnt > mid)   right = mid - 1;
            else    left = mid + 1;
        }
        return left;
    }