力扣hot100 寻找重复数 二分 抽屉原理

Problem: 287. 寻找重复数

思路

👨?🏫 参考题解

复杂度

时间复杂度: $O(N\log N)$

空间复杂度: $O(1)$

🎈 Code

class Solution {
	public int findDuplicate(int[] nums)
	{
		int n = nums.length;
		int l = 0;
		int r = n - 1;
//		二分答案法
		while (l < r)
		{
//			假设答案是 x
			int x = l + r >> 1;
			int cnt = 0;// cnt 统计 <= x 的值出现的次数
			for (int num : nums)
				if (num <= x)
					cnt++;
			if (cnt > x)//说明当前的左区间 [l,m) 里有多 
				r = x;
			else		//说明当前的右区间 (l,r) 里有多
				l = x + 1;
		}
		return l;
	}
}