一、题目粗心
给定一个蕴含 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/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
二、解题思路
这道题给咱们 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 旦行坏事，莫问前程