一、题目大意
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1:
输入:nums = [1,3,4,2,2]
输出:2
示例 2:
输入:nums = [3,1,3,4,2]
输出:3
提示:
- 1 <= n <= 105
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
进阶:
-
如何证明 nums 中至少存在一个重复的数字?
-
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
这道题给我们n+1个数,所有的数都在[1, n]区域内,首先让证明必定会有一个重复数,题目要求不能改变原数组,即不能给原数组排序,又不能用多余空间,那么hash的就不用考虑了,又要求时间小于O(n^2),只能考虑用二分搜索法了,在区间[1, n]中搜索,首先求出中点mid,然后遍历整个数组,统计所有小于等于mid的数的个数,如果个数小于等于mid,则说明重复值在[mid+1, n]之间,反之,重复值在[1, mid-1]之间,然后依次类推,直到搜索完成,此时的low就是我们要求的重复值。
三、解题方法
3.1 Java实现
public class Solution {
public int findDuplicate(int[] nums) {
int left = 1;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int num : nums) {
cnt += (num <= mid) ? 1 : 0;
}
if (cnt <= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
四、总结小记
- 2022/10/25 旦行好事,莫问前程