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

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

You are given an integer array nums and an integer k.

An integer h is called valid if all values in the array that are strictly greater than h are identical.

For example, if nums = [10, 8, 10, 8], a valid integer is h = 9 because all nums[i] > 9 are equal to 10, but 5 is not a valid integer.

You are allowed to perform the following operation on nums:

• Select an integer h that is valid for the current values in nums.
• For each index i where nums[i] > h, set nums[i] to h.

Return the minimum number of operations required to make every element in nums equal to k. If it is impossible to make all elements equal to k, return -1.

Example 1:

Input: nums = [5,2,5,4,5], k = 2

Output: 2

Explanation:

The operations can be performed in order using valid integers 4 and then 2.

Example 2:

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

Output: -1

Explanation:

It is impossible to make all the values equal to 2.

Example 3:

Input: nums = [9,7,5,3], k = 1

Output: 4

Explanation:

The operations can be performed using valid integers in the order 7, 5, 3, and

Constraints:

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

题目大意

给你一个整数数组 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 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

解题思路

• 初始化一个空的 Set 用于存储所有大于 k 的不同元素。
• 遍历数组：
  • 如果遇到小于 k 的元素，直接返回 -1。
  • 如果等于 k，跳过。
  • 如果大于 k，加入 Set。
• 最后返回 Set 的大小，即为不同的大于 k 的元素数量。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度，遍历一遍数组。
• 空间复杂度：O(n)，最坏情况下所有元素都大于 k 且互不相同，Set 最多存储 n 个元素。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function (nums, k) {
	let unique = new Set();
	for (let num of nums) {
		if (num < k) return -1;
		if (num == k) continue;
		unique.add(num);
	}
	return unique.size;
};