3289. 数字小镇中的捣蛋鬼

English Version

题目描述

数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。

为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。

返回一个长度为 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 中 恰好 包含两个重复的元素。

解法

方法一：计数

我们可以用一个数组 $\textit{cnt}$ 记录每个数字出现的次数。

遍历数组 $\textit{nums}$，当某个数字出现次数为 $2$ 时，将其加入答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。

Python3

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        cnt = Counter(nums)
        return [x for x, v in cnt.items() if v == 2]

Java

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int[] ans = new int[2];
        int[] cnt = new int[100];
        int k = 0;
        for (int x : nums) {
            if (++cnt[x] == 2) {
                ans[k++] = x;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        vector<int> ans;
        int cnt[100]{};
        for (int x : nums) {
            if (++cnt[x] == 2) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

Go

func getSneakyNumbers(nums []int) (ans []int) {
	cnt := [100]int{}
	for _, x := range nums {
		cnt[x]++
		if cnt[x] == 2 {
			ans = append(ans, x)
		}
	}
	return
}

TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const ans: number[] = [];
    const cnt: number[] = Array(100).fill(0);
    for (const x of nums) {
        if (++cnt[x] > 1) {
            ans.push(x);
        }
    }
    return ans;
}