2025-06-22：使数组的值全部为 K 的最少操作次数。用go语言，给定一个整数数组 nums 和一个整数 k。

定义整数 h 为合法的条件是：数组中所有严格大于 h 的元素值都相同。

例如，数组 nums = [10, 8, 10, 8]，h = 9 是合法的，因为数组中所有大于 9 的数都是 10，而 h = 5 不是合法的。

你可以对数组执行以下操作：

1. 选择一个整数 h，这个 h 对当前的数组 nums 来说是合法的。

2. 对数组中所有大于 h 的元素，将它们的值变为 h。

目标是通过若干次操作，把数组中的所有元素全部变成 k。请返回达到这个目标所需的 最少操作次数；如果无法实现，返回 -1。

1 <= nums.length <= 100 。

1 <= nums[i] <= 100。

1 <= k <= 100。

输入：nums = [5,2,5,4,5], k = 2。

输出：2。

解释：

依次选择合法整数 4 和 2 ，将数组全部变为 2 。

题目来自力扣3375。

示例分析

给定 nums = [5, 2, 5, 4, 5] 和 k = 2，目标是让所有元素变为 2。

初始状态

• 数组: [5, 2, 5, 4, 5]
• 需要将所有大于 2 的元素逐步变为 2。

第一步：选择合法的 h

我们需要选择一个合法的 h，即所有严格大于 h 的元素值都相同。

• 当前数组中的元素：2, 4, 5
• 严格大于 4 的元素：只有 5（满足所有严格大于 4 的元素都是 5），所以 h = 4 是合法的。
• 操作：将所有大于 4 的元素（即 5）变为 4。
• 新数组: [4, 2, 4, 4, 4]

第二步：选择合法的 h

现在数组是 [4, 2, 4, 4, 4]。

• 严格大于 2 的元素：4（所有严格大于 2 的元素都是 4），所以 h = 2 是合法的。
• 操作：将所有大于 2 的元素（即 4）变为 2。
• 新数组: [2, 2, 2, 2, 2]

结果

通过两次操作，所有元素都变为 2，因此最少操作次数是 2。

一般步骤

1. 检查可行性：如果数组中存在任何元素小于 k，则无法实现目标，直接返回 -1。
   • 因为操作只能将元素的值减小，无法增加。如果存在元素小于 k，无法通过操作将其变为 k。
2. 初始化操作次数：初始操作次数为 0。
3. 逐步操作：
   • 找到当前数组中所有严格大于 k 的元素的唯一值（如果有多个唯一值，则需要分步处理）。
   • 每次选择一个合法的 h（即当前数组中所有严格大于 h 的元素值相同），并将这些元素变为 h。
   • 每次操作后，增加操作次数。
   • 重复上述过程，直到所有元素都变为 k。
4. 返回操作次数：当所有元素都变为 k 时，返回累计的操作次数。

关键点

• 合法性检查：每次选择的 h 必须满足所有严格大于 h 的元素值相同。
• 贪心策略：每次选择当前最大的可能的 h（即尽可能一次性处理更多的元素），这样可以最小化操作次数。
• 终止条件：当所有元素都小于或等于 k 时，如果仍有元素不等于 k，则无法实现目标（但根据可行性检查，这种情况不会发生）。

时间复杂度和空间复杂度

• 时间复杂度：
  • 最坏情况下，每次操作只能处理一个唯一的元素值。例如，数组中的元素是 [100, 99, 98, ..., k+1]，每次操作只能处理一个值。
  • 由于元素值最多为 100，且 k 最小为 1，最多可能需要 100 次操作。
  • 每次操作需要遍历数组以检查合法性和更新元素，因此时间复杂度为 O(n * m)，其中 n 是数组长度，m 是可能的唯一值数量（最多 100）。
  • 因此，总的时间复杂度为 O(n * m)，即 O(100 * 100) = O(10^4)。
• 空间复杂度：
  • 主要使用一个集合来存储当前严格大于 k 的唯一值，空间复杂度为 O(m)，其中 m 是唯一值的数量（最多 100）。
  • 因此，总的空间复杂度为 O(m)，即 O(100)。

总结

• 过程：通过贪心策略，每次选择合法的 h 并尽可能减少操作次数，直到所有元素变为 k。
• 时间复杂度：O(n * m)，其中 n 是数组长度，m 是元素的最大可能值（100）。
• 空间复杂度：O(m)，用于存储唯一值。

Go完整代码如下：

.

package main

import (
	"fmt"
)

func minOperations(nums []int, k int) int {
	st := make(map[int]bool)
	for _, x := range nums {
		if x < k {
			return -1
		} else if x > k {
			st[x] = true
		}
	}
	return len(st)
}

func main() {
	nums := []int{5, 2, 5, 4, 5}
	k := 2
	fmt.Println(minOperations(nums, k))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def min_operations(nums, k):
    st = set()
    for x in nums:
        if x < k:
            return -1
        elif x > k:
            st.add(x)
    return len(st)


if __name__ == "__main__":
    nums = [5, 2, 5, 4, 5]
    k = 2
    print(min_operations(nums, k))