LeetCode.3375. 使数组的值全部为 K 的最少操作次数

3375. 使数组的值全部为 K 的最少操作次数

给你一个整数数组 nums 和一个整数 k 。
如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。
比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。
你可以对 nums 执行以下操作：

• 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
• 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。
  你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

示例 1：
输入：nums = [5,2,5,4,5], k = 2
输出：2
解释：依次选择合法整数 4 和 2 ，将数组全部变为 2 。示例 2：
输入：nums = [2,1,2], k = 2
输出：-1
解释：没法将所有值变为 2 。示例 3：
输入：nums = [9,7,5,3], k = 1
输出：4
解释：依次选择合法整数 7 ，5 ，3 和 1 ，将数组全部变为 1 。

解题思路：

1. 调用 bubble_sort 函数对数组 nums 进行升序排序。
2. 排序后，数组中的元素按从小到大的顺序排列，方便后续统计不同的大于 k 的元素。
3. 遍历排序后的数组，统计大于 k 的不同元素的个数。

void bubble_sort(int* nums, int numsSize)
{for (int i = 0; i < numsSize; i++){for (int j = 0; j < numsSize -1 - i; j++){if (nums[j] > nums[j + 1]){int tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}
}
int minOperations(int* nums, int numsSize, int k) {for(int i=0;i < numsSize;i++){if(nums[i]<k){return -1;}}bubble_sort(nums,numsSize);int count=0;for(int i = 0; i < numsSize; i++){if(nums[i]>k){k=nums[i];count++;}}return count;
}

优化---->

1. 检查元素下限：先遍历数组 nums，若发现有小于 k 的元素，直接返回 -1。
2. 使用哈希表记录元素：
   • 定义一个长度为 MAX_VALUE 的数组 hash 来模拟哈希表，初始时所有元素都为 0。
   • 再次遍历数组 nums，对于大于 k 的元素，如果其在 hash 表中对应的位置为 0，说明是一个新的不同元素，将该位置置为 1 并增加 distinct_count。
3. 返回结果：最终返回 distinct_count，即大于 k 的不同元素的数量，也就是最少操作次数。

int minOperations(int* nums, int numsSize, int k) {// 检查是否有小于 k 的元素，若有则无法完成目标，返回 -1for (int i = 0; i < numsSize; i++) {if (nums[i] < k) {return -1;}}// 用数组模拟哈希表，初始化为 0int hash[101] = {0};int distinct_count = 0;// 遍历数组，标记大于 k 的元素for (int i = 0; i < numsSize; i++) {if (nums[i] > k && hash[nums[i]] == 0) {hash[nums[i]] = 1;distinct_count++;}}return distinct_count;
}