3396. 使数组元素互不相同所需的最少操作次数

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

You are given an integer array nums. You need to ensure that the elements in the array are distinct. To achieve this, you can perform the following operation any number of times:

• Remove 3 elements from the beginning of the array. If the array has fewer than 3 elements, remove all remaining elements.

Note that an empty array is considered to have distinct elements. Return the minimum number of operations needed to make the elements in the array distinct.

Example 1:

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

Output: 2

Explanation:

• In the first operation, the first 3 elements are removed, resulting in the array [4, 2, 3, 3, 5, 7].
• In the second operation, the next 3 elements are removed, resulting in the array [3, 5, 7], which has distinct elements.

Therefore, the answer is 2.

Example 2:

Input: nums = [4,5,6,4,4]

Output: 2

Explanation:

• In the first operation, the first 3 elements are removed, resulting in the array [4, 4].
• In the second operation, all remaining elements are removed, resulting in an empty array.

Therefore, the answer is 2.

Example 3:

Input: nums = [6,7,8,9]

Output: 0

Explanation:

The array already contains distinct elements. Therefore, the answer is 0.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

题目大意

给你一个整数数组 nums，你需要确保数组中的元素 **互不相同 **。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

注意： 空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 **最少操作次数 **。

示例 1：

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

输出： 2

解释：

• 第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
• 第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。

因此，答案是 2。

示例 2：

输入： nums = [4,5,6,4,4]

输出： 2

解释：

• 第一次操作：移除前 3 个元素，数组变为 [4, 4]。
• 第二次操作：移除所有剩余元素，数组变为空。

因此，答案是 2。

示例 3：

输入： nums = [6,7,8,9]

输出： 0

解释：

数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题思路

1. 使用 Set 记录已出现的元素
   我们用一个 Set 来存储已经遍历过的元素，用于检测是否有重复元素出现。

2. 从数组末尾向前遍历
   从数组最后一个元素开始，向前遍历，这样做的目的可能是为了确保第一次重复出现的元素是离数组末尾越近越好。

3. 检测重复
   每次遍历到一个元素时，如果这个元素已经存在于 seen 集合中，说明它是一个重复值。

4. 计算结果
   一旦找到重复元素，用下标 i 计算出操作次数 Math.floor(i / 3) + 1，返回这个结果。

5. 无重复时返回 0
   如果遍历完成都没有发现重复元素，则返回 0。

复杂度分析

• 时间复杂度：O(n)，最多遍历数组一次。
• 空间复杂度：O(n)，哈希表中最多存储 n 个数字。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function (nums) {
	let seen = new Set();

	for (let i = nums.length - 1; i >= 0; i--) {
		if (seen.has(nums[i])) {
			return Math.floor(i / 3) + 1;
		}
		seen.add(nums[i]);
	}
	return 0;
};

相关题目

题号	标题	题解	标签	难度	力扣
945	使数组唯一的最小增量	[✓]	贪心 数组 计数 1+	🟠	🀄️ 🔗