[LeetCode] 每日一题 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 。

题目链接

https://leetcode.cn/problems/minimum-operations-to-make-array-values-equal-to-k

示例输入

示例 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

解题思路

这道题看似复杂，但实际上只是一个简单的脑筋急转弯。一开始，我也试图通过排序和模拟来解决，但发现问题并不需要这么复杂的操作。

题目给定了两个关键点：

1. 如果我们选择一个整数 h，它对于当前数组中所有 nums[i] > h 的数值都应该相等。

2. 最终，我们要将所有数组元素变成 k。

如果 k 大于数组中的最小元素，那么我们就不可能通过合法的 h 使得所有元素变成 k，因为不可能将比 k 小的元素变成更大的 k。在这种情况下，直接返回 -1。

如果 k 小于或等于数组中的最小值，我们只需要统计所有 大于 k 的元素个数，这个数量就是我们所需要的操作次数。因为每次操作我们只能改变大于 h 的元素，所以我们只需处理那些大于 k 的元素。

class Solution {
    public int minOperations(int[] nums, int k) {
        int min = Integer.MAX_VALUE;
        boolean[] contains = new boolean[101];
        int count = 0;
        for (int num : nums) {
            if (num != k && !contains[num]) {
                count++;
                contains[num] = true;
            }
            min = Math.min(min, num);
        }
        return k <= min ? count : -1;
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历数组一次，进行常数时间的操作。这里 n 是数组 nums 的长度 ⚡️

• 空间复杂度：O(1)，只用了一个大小为 101 的布尔数组来存储已处理的元素。空间开销非常小 🔋

总结

这道题让我再次体会到 简单问题 的 巧妙转化。刚开始看时，我觉得可能需要模拟和排序，但其实只要注意到数组中元素的大小关系，就能迅速解决问题。通过这种思路，我们有效地 降低了复杂度，从而快速得到答案。

这类问题给了我一个提醒——很多看起来复杂的题目，可能只是一个简单的 数学推理 或 条件判断。找准关键点后，就能让问题迎刃而解 😎

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。