Easy

题目描述

在数字村中，有一个名为 nums 的数字列表，包含从 0 到 n-1 的整数。每个数字本应在列表中只出现一次，然而，两个调皮的数字偷偷地多出现了一次，使得列表比平常更长。

作为村里的侦探，你的任务是找到这两个调皮的数字。返回一个大小为 2 的数组，包含这两个数字（顺序任意），这样数字村就能恢复平静了。

示例 1：

输入：nums = [0,1,1,0]
输出：[0,1]
解释：数字 0 和 1 在数组中各出现两次。

示例 2：

输入：nums = [0,3,2,1,3,2]
输出：[2,3]
解释：数字 2 和 3 在数组中各出现两次。

示例 3：

输入：nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出：[4,5]
解释：数字 4 和 5 在数组中各出现两次。

约束条件：

  • 2 <= n <= 100
  • nums.length == n + 2
  • 0 <= nums[i] < n
  • 输入保证 nums 恰好包含两个重复元素。

解题思路

这是一个经典的寻找重复元素问题，有多种解法：

方法一：哈希表计数（推荐） 使用哈希表统计每个数字的出现次数，找出出现次数为2的两个数字。这是最直观的解法，时间复杂度为O(n)，空间复杂度为O(n)。

方法二：排序法 先对数组排序，然后遍历找到相邻重复的元素。时间复杂度为O(n log n)，空间复杂度为O(1)。

方法三：数学法（异或运算） 由于每个数字0到n-1应该出现一次，而有两个数字多出现了一次，可以利用异或运算的性质。但需要结合其他技巧来分离两个重复数字。

方法四：原地修改 利用数组索引，通过标记访问过的位置来找出重复元素。由于数字范围是0到n-1，可以使用负号作为标记。

考虑到代码的简洁性和可读性，推荐使用哈希表计数的方法。

代码实现

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        unordered_map<int, int> count;
        vector<int> result;
        
        for (int num : nums) {
            count[num]++;
            if (count[num] == 2) {
                result.push_back(num);
            }
        }
        
        return result;
    }
};

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        count = {}
        result = []
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if count[num] == 2:
                result.append(num)
        
        return result

public class Solution {
    public int[] GetSneakyNumbers(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        List<int> result = new List<int>();
        
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
            
            if (count[num] == 2) {
                result.Add(num);
            }
        }
        
        return result.ToArray();
    }
}

var getSneakyNumbers = function(nums) {
    const seen = new Set();
    const result = [];
    
    for (const num of nums) {
        if (seen.has(num)) {
            result.push(num);
        } else {
            seen.add(num);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表计数O(n)O(n)
排序法O(n log n)O(1)
原地修改O(n)O(1)

其中 n 是数组的长度。哈希表方法在时间效率上最优，适合大多数场景。

相关题目