python3 解法, 执行用时: 88 ms, 内存消耗: 26 MB, 提交时间: 2022-11-27 13:11:40

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = nums[0], nums[nums[0]]
        while slow != fast:
            slow, fast = nums[slow],  nums[nums[fast]]
        
        pre1, pre2 = 0, slow
        while pre1 != pre2:
            pre1, pre2 = nums[pre1], nums[pre2]
        
        return pre1

java 解法, 执行用时: 4 ms, 内存消耗: 59 MB, 提交时间: 2022-11-27 13:09:11

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int pre1 = 0;
        int pre2 = slow;
        while(pre1 != pre2){
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
}

javascript 解法, 执行用时: 76 ms, 内存消耗: 48.8 MB, 提交时间: 2022-11-27 13:08:39

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

golang 解法, 执行用时: 76 ms, 内存消耗: 8.2 MB, 提交时间: 2022-11-27 13:08:09

func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] { }
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

golang 解法, 执行用时: 84 ms, 内存消耗: 8.2 MB, 提交时间: 2022-11-27 13:07:55

func findDuplicate(nums []int) int {
    n := len(nums)
    ans := 0
    bit_max := 31
    for ((n-1) >> bit_max) == 0 {
        bit_max--
    }
    for bit := 0; bit <= bit_max; bit++ {
        x, y := 0, 0
        for i := 0; i < n; i++ {
            if (nums[i] & (1 << bit)) > 0 {
                x++
            }
            if i >= 1 && (i & (1 << bit)) > 0 {
                y++
            }
        }
        if x > y {
            ans |= 1 << bit
        }
    }
    return ans
}

javascript 解法, 执行用时: 124 ms, 内存消耗: 48 MB, 提交时间: 2022-11-27 13:07:40

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    const n = nums.length;
    let ans = 0;
    // 确定二进制下最高位是多少
    let bit_max = 31;
    while (!((n - 1) >> bit_max)) {
        bit_max -= 1;
    }
    for (let bit = 0; bit <= bit_max; ++bit) {
        let x = 0, y = 0;
        for (let i = 0; i < n; ++i) {
            if (nums[i] & (1 << bit)) {
                x += 1;
            }
            if (i >= 1 && (i & (1 << bit))) {
                y += 1;
            }
        }
        if (x > y) {
            ans |= 1 << bit;
        }
    }
    return ans;
};

javascript 解法, 执行用时: 80 ms, 内存消耗: 48.5 MB, 提交时间: 2022-11-27 13:07:26

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    const n = nums.length;
    let l = 1, r = n - 1, ans = -1;
    while (l <= r) {
        let mid = (l + r) >> 1;
        let cnt = 0;
        for (let i = 0; i < n; ++i) {
            cnt += nums[i] <= mid;
        }
        if (cnt <= mid) {
            l = mid + 1;
        } else {
            r = mid - 1;
            ans = mid;
        }
    }
    return ans;
};

golang 解法, 执行用时: 72 ms, 内存消耗: 8.2 MB, 提交时间: 2022-11-27 13:07:10

func findDuplicate(nums []int) int {
    n := len(nums)
    l, r := 1, n - 1
    ans := -1
    for l <= r {
        mid := (l + r) >> 1
        cnt := 0
        for i := 0; i < n; i++ {
            if nums[i] <= mid {
                cnt++
            }
        }
        if cnt <= mid {
            l = mid + 1
        } else {
            r = mid - 1
            ans = mid
        }
    }
    return ans
}