287.寻找重复数.md

287.寻找重复数

/*
 * @lc app=leetcode.cn id=287 lang=typescript
 *
 * [287] 寻找重复数
 */

// @lc code=start
function findDuplicate(nums: number[]): number {}
// @lc code=end

解法 1: 位运算

• https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/

function findDuplicate(nums: number[]): number {
  let maxBit = 31
  const n = nums.length
  while (!((n - 1) >> maxBit)) {
    maxBit--
  }
  let res = 0
  for (let i = 0; i <= maxBit; i++) {
    const bit = 1 << i
    let [x, y] = [0, 0]
    for (let j = 0; j < nums.length; j++) {
      if (nums[j] & bit) x++
      if (j && j & bit) y++
    }
    if (x > y) res |= bit
  }
  return res
}

Case

test.each([
  { input: { nums: [1, 3, 4, 2, 2] }, output: 2 },
  { input: { nums: [3, 1, 3, 4, 2] }, output: 3 },
  { input: { nums: [1, 1] }, output: 1 },
  { input: { nums: [1, 1, 2] }, output: 1 },
  { input: { nums: [2, 2, 2, 2, 2] }, output: 2 },
  { input: { nums: [1, 2, 2] }, output: 2 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(findDuplicate(nums)).toEqual(output)
})