LC 961. 在长度 2N 的数组中找出重复 N 次的元素

题目描述

这是 LeetCode 上的 961. 在长度 2N 的数组中找出重复 N 次的元素 ,难度为 简单

给你一个整数数组 nums ,该数组具有以下属性:

  • $nums.length == 2 \times n$
  • nums 包含 $n + 1$ 个 不同的 元素
  • nums 中恰有一个元素重复 $n$ 次

找出并返回重复了 $n$ 次的那个元素。

示例 1:

1
2
3
输入:nums = [1,2,3,3]

输出:3

示例 2:
1
2
3
输入:nums = [2,1,2,5,3,2]

输出:2

示例 3:
1
2
3
输入:nums = [5,1,5,2,5,3,5,4]

输出:5

提示:

  • $2 <= n <= 50004
  • $nums.length == 2 \times n$
  • $0 <= nums[i] <= 10^4$
  • nums 由 $n + 1$ 个 不同的 元素组成,且其中一个元素恰好重复 $n$ 次

计数模拟

根据题目给定的三个条件可推断出:数组中仅有一个元素出现多次,其余元素均出现一次。

又利用数据范围为 $10^4$,我们可以使用数组充当哈希表进行计数,当出现一个 $nums[i]$ 重复出现即是答案。

代码:

1
2
3
4
5
6
7
8
9
class Solution {
int[] cnts = new int[10010];
public int repeatedNTimes(int[] nums) {
for (int x : nums) {
if (++cnts[x] > 1) return x;
}
return -1;
}
}

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(C)$

构造共性

假设重复出现的数字是 $x$,数字 $x$ 重复了 $n$ 次,要将这 $n$ 个相同的 $x$ 间隔开,需要 $n - 1$ 个额外数字,而实际上我们除 $x$ 以外还有 $n$ 个额外数字(数字总数为 $n + 1$ 个),因此在我们所能构造出的所有排列方式中,最多 使相邻 $x$ 之间间隔了 $2$ 个额外数字。

对于每个 $nums[i]$ 而言,我们检查往前的三个位置(若有),如果有重复相等情况,说明当前的 $nums[i]$ 即是答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int repeatedNTimes(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int t = nums[i];
if (i - 1 >= 0 && nums[i - 1] == t) return t;
if (i - 2 >= 0 && nums[i - 2] == t) return t;
if (i - 3 >= 0 && nums[i - 3] == t) return t;
}
return -1;
}
}

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.961 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!