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

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

给你一个整数数组 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 个元素（若元素不足 3 个则移除剩余元素），直至数组中元素互不相同。

// 判断数组中是否存在重复元素
int hasDuplicates(int* nums, int numsSize) {for (int i = 0; i < numsSize; i++) {for (int j = i + 1; j < numsSize; j++) {if (nums[i] == nums[j]) {return 1;}}}return 0;
}// 计算使数组元素互不相同的最少操作次数
int minimumOperations(int* nums, int numsSize) {int operations = 0;while (hasDuplicates(nums, numsSize)) {if (numsSize >= 3) {// 移除开头的 3 个元素for (int i = 0; i < numsSize - 3; i++) {nums[i] = nums[i + 3];}numsSize -= 3;} else {// 若元素不足 3 个，移除剩余元素numsSize = 0;}operations++;}return operations;
}

1. hasDuplicates 函数：该函数用于判断数组中是否存在重复元素。通过两层嵌套循环遍历数组，若找到两个相同的元素则返回 1，表示存在重复元素；若遍历完整个数组都未找到重复元素，则返回 0。
2. minimumOperations 函数：
   • 初始化操作次数 operations 为 0。
   • 使用 while 循环，只要数组中存在重复元素，就继续进行操作。
   • 若数组元素数量大于等于 3，则移除开头的 3 个元素，通过将后面的元素依次向前移动覆盖前面的元素实现。
   • 若数组元素数量小于 3，则将数组元素数量置为 0，表示移除所有剩余元素。
   • 每次操作后，操作次数 operations 加 1。
   • 当数组中不存在重复元素时，循环结束，返回操作次数。