题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n - 1 的范围内。数组中某些数字是重复的, 但不知道有几个数字重复了, 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:

[2, 3, 1, 0, 2, 5, 3]
输出: 2 或 3 

限制:

2 <= n <= 100000

来源: 力扣LeetCode (opens new window)

解题思路 or 实现原理

1. 遍历该数组, 检查是否出现过, 首次出现过就标识, 再次出现就返回该值。

2. 由于题目限定了所有数字都在 0～n - 1 的范围内, 即元素位置 index 取到的值 也会在当前数组的范围内, 所以只需要遍历该数组, 如果遍历的值不等于当前的 index, 就把它放到对应的值位置上, 如果该位置上存在该值, 结果就是该值。

实现代码

/*
 * @Author: Rainy
 * @Date: 2019-11-14 19:25:01
 * @LastEditors: Rainy
 * @LastEditTime: 2020-07-26 10:52:46
 */

import { ObjectMap } from "types";

/**
 * @param {number[]} nums
 * @return {number}
 */
export function findRepeatNumber_1(nums: number[]): number | undefined {
    const map: ObjectMap<boolean> = {};
    for (const num of nums) {
        if (!map[num]) {
            map[num] = true;
        } else {
            return num;
        }
    }
}

export function findRepeatNumber_2(nums: number[]): number | undefined {
    let num: number;
    for (let index = 0; index < nums.length; index++) {
        while ((num = nums[index]) !== index) {
            if (num === nums[num]) {
                return num;
            }

            [nums[num], nums[index]] = [nums[index], nums[num]];
        }
    }
}