LeetCode 287. 寻找重复数

// hash表，空间复杂度为O(n)，不满足题目进阶要求// func findDuplicate(nums []int) int {//     m := make(map[int]int)//     for i := 0; i < len(nums); i++ {//         m[nums[i]] += 1//         if m[nums[i]] >= 2 {//             return nums[i]//         }//     }//     return -1// }// 二分法 ：// 参考B站视频题解：https://www.bilibili.com/video/BV1qg41137Fg/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4// 思路:每一次找中间值，考虑到1-n之间的数一定都会出现，如果非重复情况下每个数只会出现一次，故我们判断小于等于中间值元素个数如果超过了中间值则说明重复的数在左半边，否则去右半边找/* 举例说明正常情况下【不包含重复元素】：小于等于midVal值的个数cnt应该是与midVal值恰好相等的比如表示范围为[1,n=4]的nums=[1,2,3,4]中，小于等于2的元素一共有2个：1和2但在实际情况下【包含重复元素】，比如说 nums=[1,3,4,2,2]，那么怎么样找出这个重复的2呢？我们可以先推理出表示范围为[1,n=4]，且正常情况下【不包含重复元素】的中间值：midVal = 1 + (4-1)/2 = 2接着我们遍历 实际情况下【包含重复元素】的nums=[1,3,4,2,2]，发现其中小于等于 midVal=2 的数实际上有3个，分别为 1,2,2，大于正常情况下的2个因此可以判断在实际给出的nums=[1,3,4,2,2]中，存在多余且重复的数，导致小于等于 midVal=2 的元素个数为3个（正常情况下应该为2个）*/// 时间复杂度：二分法 O(nlogn)，空间复杂度：O(1)funcfindDuplicate(nums []int) int {
// nums的数字都在 [1, n] 范围内，所以先定位nums中元素的【值】可能出现的左右范围 low和high// 数组 nums包含n + 1 个整数，即 n + 1 = len(nums)，因此 n = len(nums) - 1n :=len(nums)
low, high :=1, n-1forlow<=high {
midVal, cnt :=low+ (high-low) /2, 0// 统计nums中元素在区间为[1, midVal]中的个数，注意这里midVal表示的是 正常情况下【不包含重复元素】的中间值fori :=0; i<n; i++ {
// 统计实际给出的nums中，小于等于midVal值的元素个数，正常情况下【不包含重复元素】应该是cnt刚好等于midValifnums[i] <=midVal {
cnt++            }
        }
// 发现cnt大于正常情况下【不包含重复元素】对应的元素个数 midVal，并且这个重复数是小于midVal的ifcnt>midVal {
high=midVal-1// 发现cnt小于正常情况下【不包含重复元素】对应的元素个数 midVal，那就说明要找的重复数存在于大于midVal的右侧        } else {
low=midVal+1        }
    }
returnlow}