LeetCode 442. 数组中重复的数据

Categories:

题目描述
思路分析
1. 解法一：原地标记（推荐）
相似题目

题目描述

✅ 442. 数组中重复的数据

思路分析

解法一：原地标记（推荐）

核心思路：

数组元素范围为 1..n，可用下标映射。

对每个数 x，访问下标 abs(x) - 1，将该位置取负表示出现过。

若该位置已为负，说明 x 是重复元素。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，不计输出所用空间。

import java.util.*;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] < 0) {
                res.add(idx + 1);
            } else {
                nums[idx] = -nums[idx];
            }
        }
        return res;
    }
}

func findDuplicates(nums []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		idx := nums[i]
		if idx < 0 {
			idx = -idx
		}
		idx--
		if nums[idx] < 0 {
			res = append(res, idx+1)
		} else {
			nums[idx] = -nums[idx]
		}
	}
	return res
}

相似题目

题目	难度	考察点
287. 寻找重复数	中等	原地标记
448. 找到所有数组中消失的数字	简单	原地标记
41. 缺失的第一个正数	困难	原地标记
268. 丢失的数字	简单	原地标记
645. 错误的集合	简单	原地标记

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/16273730