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

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique elements.
• Exactly one element of nums is repeated n times.

Return the element that is repeatedn times.

Example 1:

Input: nums = [1,2,3,3]

Output: 3

Example 2:

Input: nums = [2,1,2,5,3,2]

Output: 2

Example 3:

Input: nums = [5,1,5,2,5,3,5,4]

Output: 5

Constraints:

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

题目大意

给你一个整数数组 nums ，该数组具有以下属性：

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

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

示例 1：

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

输出： 3

示例 2：

输入： nums = [2,1,2,5,3,2]

输出： 2

示例 3：

输入： nums = [5,1,5,2,5,3,5,4]

输出： 5

提示：

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

解题思路

1. 核心思路：

   • 给定数组总长度为 2N，仅一个元素重复了 N 次，其余的元素各出现 1 次。
   • 这意味着重复元素在数组中一定会出现多次，且相邻或间隔的某些位置上一定会包含它。
   • 最分散的情况是，每个长度为 2 的子数组恰好有 1 个重复元素，这意味着从重复元素开始的长度为 4 的子数组将有 2 个主元素。
   • 因此，我们只需要将元素与距离为 1、2 或 3 的邻居进行比较，找出重复元素即可。
   • 之所以最多只需检查后 3 位，是因为无论元素如何排列，总有两个重复的元素会落在任意连续 4 个位置之中。

2. 逐个检查可能的重复：

   • 遍历数组时，通过比较当前元素与后续几位（最多检查 3 位）的元素是否相同，可以快速定位重复的元素。

3. 提前终止：

   • 一旦发现某个元素重复，即可直接返回该元素，无需继续遍历。

复杂度分析

• 时间复杂度: O(n)，在最坏情况下，可能需要遍历整个数组（每个元素最多比较 3 次），时间复杂度依然线性。
• 空间复杂度: O(1)，仅使用常量级变量，通过就地比较，不需要使用额外的数据结构（如哈希表），优化了空间复杂度。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
	const n = nums.length;
	for (let i = 0; i < n; i++) {
		if (
			nums[i] === nums[i + 1] ||
			nums[i] === nums[i + 2] ||
			nums[i] === nums[i + 3]
		) {
			return nums[i];
		}
	}
};