二十二查找重复数字

2020-12-01 22:50 JavaScript技术分享

题:

给你一个长度为n+1的数组,数组中每一项都大于等于1,小于等于n,证明数组至少存在一个重复的数字,并返回该数字。


思路:

  • 时间复杂度:O(n*log(n))。

  • 空间复杂度:O(1)。

  • 目标数组[2,1,3,2,4] => 长度为n+1=5 => n = 4。

  • 目标数组应该是1到4中的数字。

  • 最小数字low为1,最大数字high为4,中间mid数字为(low+high)/2 = 2。

  • 其中目标数组小于等于mid有3个数字,low到mid中有3个数字,说明有重复项,更新high为mid,因此high为2,更新mid为(low+high)/2 = 1。

  • 其中目标数组小于等于mid有1个数字,大于mid有4个数字,说明4个数字中有重复项,更新low为mid+1,此时low为2。

  • 因为low === high  都为2,所以该目标数组重复项为2。

算法如下


/** * @description 查找重复数字 * @param {Array} nums 目标数组 */function findRepeatNumber(nums) {    let low = 1, high = nums.length - 1    // 当low 等于 high退出循环    while (low < high) {        let mid = Math.floor((low+high)/2)        let count = 0        for (let i = 0; i < nums.length; i++) {            // 求目标数组中小于等于mid数量            if(nums[i] <= mid) count++        }        // 如果数量大于mid,说明重复项在 low ~ mid之间        if(count > mid) high = mid        // 否则 重复项在mid+1 ~ high之间        else low = mid+1    }    // 返回重复数字    return low}


本文章转载自公众号:gh_22f6286a7605

首页 - JavaScript 相关的更多文章: