给定一个包含 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:以时间换空间 不用hash表,直接for循环一一比对
解法2:以空间换时间 用到hash表去重
这是最常用的方法,而且实际情况中往往采用以空间换时间的策略。
解法3:使用二分查找, 二分查找的解题信号往往是在给定范围内去寻找一个数,根据寻找结果再缩小寻找范围时间复杂度为ologn。
二分查找的思路如下:
抽屉原理:假如我们有n个抽屉,往n个抽屉里面放n + 1个数,那么必定有一个抽屉里面是重复放的。
二分查找原理: 我们猜测一个数比如是 mid ,统计nums数组中小于等于mid的数的个数,如果发现个数大于mid,证明在 1 - mid这些数中,存在一个数在nums数组中是重复的。
举个例子,假如1 - 3 ,mid是2,给定nums数组是 1 2 2 3,那么统计小于等于2 的数量就是3 > mid ,所以 在 1 - mid 这个区间里面存在一个数,该数在nums数组中是重复的。
所以,我们寻找完数、判断完数、就该缩小寻找范围了,如果count > mid,那么就往1 - mid中找,反之往 mid + 1 - length 中找。
总结一下:二分查找就是在给定范围内找出一个数,找到一个数我们就根据规则判断该数是否符合,根据符合的情况进一步缩小范围,在最后的边界值判断时候,举一个例子带入算法更容易判断边界值。
package leetcode.lc20221205;
/*
* @author lzy
* @version 1.0
* @DESC 寻找一个重复数
* */
public class Solution01 {
//本题有三种解法
public int findDuplicate(int[] nums) {
//解法1:以时间换空间 不用hash表,直接for循环一一比对
//解法2:以空间换时间 用到hash表去重
//解法3:使用二分查找, 二分查找的解题信号往往是在给定范围内去寻找一个数,根据寻找结果再缩小寻找范围
//时间复杂度为ologn
//举例子:1 2 2 3 / 1 2 3
int length = nums.length;
int left = 1;
int right = length;
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count > mid) {
//也有可能是mid
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}