LeetCode 剑指 Offer 03. 数组中重复的数字

Categories:

题目描述
思路分析
1. 解法一：哈希集合（推荐）
2. 解法二：原地置换
相似题目

题目描述

✅ 剑指 Offer 03. 数组中重复的数字

思路分析

解法一：哈希集合（推荐）

核心思路：

用一个哈希集合记录已经出现过的数字。

遍历数组，若当前数字已在集合中，则该数字即为重复数字，直接返回。

否则将当前数字加入集合，继续遍历。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需遍历一次数组。

空间复杂度：O(n)，哈希集合最多存储 n 个元素。

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 使用哈希集合记录已出现的数字
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // 若已存在则直接返回重复数字
            if (!seen.add(num)) {
                return num;
            }
        }
        return -1;
    }
}

func findRepeatNumber(nums []int) int {
    // 使用哈希集合记录已出现的数字
    seen := make(map[int]bool)
    for _, num := range nums {
        // 若已存在则直接返回重复数字
        if seen[num] {
            return num
        }
        seen[num] = true
    }
    return -1
}

解法二：原地置换

核心思路：

数组长度为 n，所有数字范围在 0 ~ n-1，因此每个数字理论上可以放到与其值相等的下标位置（即 nums[i] 应放在下标 i 处）。

遍历数组，对于位置 i 上的数字 nums[i]：

若 nums[i] == i，已在正确位置，跳过。

若 nums[i] == nums[nums[i]]，说明下标 nums[i] 处已存放了相同的数字，找到重复，返回。

否则，将 nums[i] 与 nums[nums[i]] 交换，把 nums[i] 放到正确位置。

该方法利用数组本身作为哈希表，无需额外空间。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，每个数字最多被移动一次。

空间复杂度：O(1)，原地操作，不使用额外空间。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            // 当前数字已在正确位置，跳过
            if (nums[i] == i) {
                i++;
                continue;
            }
            // nums[i] 与 nums[nums[i]] 相同，找到重复数字
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            // 将 nums[i] 交换到其应在的位置 nums[i]
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); {
        // 当前数字已在正确位置，跳过
        if nums[i] == i {
            i++
            continue
        }
        // nums[i] 与 nums[nums[i]] 相同，找到重复数字
        if nums[i] == nums[nums[i]] {
            return nums[i]
        }
        // 将 nums[i] 交换到其应在的位置
        nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
    }
    return -1
}

相似题目

题目	难度	考察点
287. 寻找重复数	中等	原地哈希 / 快慢指针（Floyd）
442. 数组中重复的数据	中等	原地哈希 / 负数标记
41. 缺失的第一个正数	困难	原地哈希 / 数组标记
268. 丢失的数字	简单	哈希表 / 数学 / 位运算
645. 错误的集合	简单	哈希表 / 数组标记
剑指 Offer 61. 扑克牌中的顺子	简单	哈希表 / 排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/95111759