leetcode287(寻找重复数)--C语言实现
< 返回列表时间: 2020-05-26来源:OSCHINA
求:
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。

解:
思路:使用常规的数组遍历方法很容易获得答案,但是时间复杂度是O(N^2),而题目要求时间复杂度小于O(N^2)。我们也容易想到使用哈希表存储数字出现的次数,但这违反了只能使用O(1)的额外空间的约束。因此本题得到的算法,我们可以认为并不要求时间复杂度最优,而是使用部分时间换取空间,在时空效率上达到一个相对的平衡。(实际生产中时间换空间是少见的,本题具有特殊性)
常规方法如下:
int findDuplicate( int * nums, int numsSize){ int i,j; for (i= 0 ;i<numsSize;i++){ for (j=i+ 1 ;j<numsSize;j++){ if (nums[i]==nums[j]) return nums[i]; } } return 0 ; }
因此我们进一步进行优化,我们先假设没有重复数,设cnt[i]为小于等于i的个数,那么对区间[1,N]上的每一个数,均出现一次,均满足:cnt[i]=i。现在我们假设在区间[1,N]中的某个位置(设为target)加入一个重复的数。加入重复的数后,对任意i<target,cnt[i]=i不受影响。对任意i>=target,cnt[i]=i+1>i。以上假设target对应的数仅重复了一次,如果我们让这个数重复多次,那么可以认为我们使用target位置上的数去对其他位置的数进行了若干次替换。如果替换的数小于target,那么对i<target,cnt[i]<=i。如果替换的数大于target,替换后依然保持cnt[i]>i。 因此我们可以得到,如果target是我们的目标结果,则对i<target,总是有cnt[i]<=i。对i>target,总是有cnt[i]>i。因此我们使用二分查找的方法,令low=0,high=numsSize-1,每次取区间中值mid,遍历原数组后如果cnt[mid]<=mid,说明结果在[mid+1,high]的分支中,更新low为mid+1,继续查找。如果cnt[mid]>mid,说明结果在[low,mid-1]的分支中,更新high为mid-1,记录当前的i,继续查找直到low==high。返回此时的i,即为所求的target。 int findDuplicate( int * nums, int numsSize){ int i,mid,ret; int low = 1 ; int high = numsSize- 1 ; while (low<=high){ int count = 0 ; mid = (low+high)>> 1 ; for (i= 0 ;i<numsSize;i++) if (nums[i]<=mid) ++count; if (count <= mid){ low = mid+ 1 ; } else { high = mid - 1 ; ret = mid; } } return ret; }
热门排行