287.寻找重复数 二分法 双指针

  https://leetcode-cn.com/problems/find-the-duplicate-number/

简单思路：

　　1. return sum( nums ) - n*(n+1)/2

　　2. set()  if num in set: return num              用set 

　　3. nums.sort()  if nums[i] == nums[i+1] : return nums[ i ]              排序后 相同的数相邻

本题思路：

　　1. 由于不能使用外部空间，并且时间复杂度< n^2，自然想到 nlogn, 就是二分法

　　2. 双指针 快慢指针法，没看懂，放弃了 - -  

二分法注意点：

　　1. 边界选取用中值左边界。   mid = low + (high - low)//2    

　　　　而不是  mid = (low + high+1)//2

　　2. 想清楚数数的两个判断条件

　　　　1） 判断nums[i] 与 mid的关系时 是小于等于：   if nums[ i ] <= mid : count +=1。

　　　　2） 这意味着统计了包括中值以下的所有数，如果重复数在里面 则必有  count > mid 。  比如 0-7中，mid = 4 ; count = 5; 此时移动上界为4，在0-4中找

　　　　　　if count > mid:  high = mid

　　　　　　else: low = mid + 1

　　　　　    否则在 5-7中找重复的数

　　3. 最后返回左值，我还没想清楚

代码：

287.寻找重复数 二分法 双指针

原文：https://www.cnblogs.com/ChevisZhang/p/12845712.html