哈希表

算法

发布日期: 2023-06-29

更新日期: 2024-12-20

原地交换

题义中 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内，此说明含义：数组元素的索引和值是 一对多 的关系。

可遍历数组并通过交换操作，使元素的索引与值一一对应（即 nums[i] = i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

第一次遇到数字 $x$ 时，将其交换至索引 $x$ 处；当第二次遇到数字 $x$ 时，一定有 nums[x] = x ，此时即可得到一组重复数字。

算法流程：

遍历数组 $nums$，设索引初始值 $i=0$
- 若 $nums[i] = i$：说明此数字已在对应索引位置，无需交换，因此跳过；
- 若 $nums[nums[i]] = nums[i]$：说明索引 $nums[i]$ 处和索引 $i$ 处元素值相等，即找到重复值；
- 否则：交换索引 $nums[i]$ 处和索引 $i$ 处元素值，使得 $nums[i]=i$
若遍历完毕尚未返回，则返回 -1

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}