今天和大家聊的问题叫做 寻找重复数，我们先来看题面：https://leetcode-cn.com/problems/find-the-duplicate-number/
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
给定一个包含 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 示例 3： 输入：nums = [1,1] 输出：1 示例 4： 输入：nums = [1,1,2] 输出：1
解题
二分查找法
class Solution { public int findDuplicate(int[] nums) { int low = 1,high = nums.length,mid = 0; while(low < high) { mid = low + (high-low)/2; //System.out.println(low+" "+high+" "+mid); int count = 0; for(int num:nums) { if(num <= mid) { count++; } } if(count > mid) { //如果严格大于的话，说明在（0，mid）这个范围内肯定有重复的元素 high = mid; }else { low = mid+1; } } return low; } }
快慢指针判断是否有环
class Solution { public int findDuplicate(int[] nums) { int fast = 0,slow = 0; do { //因为数组元素范围都在1~n，所以不会越界 slow = nums[slow]; fast = nums[fast]; fast = nums[fast]; }while(fast != slow); //fast和slow相交的地方并不是环形入口 slow = 0; //A = C找环形入口 while(slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
