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

1，问题描述

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 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

2，初步思考

​ 问题转化为：

​ 1️⃣不存在小于k的数据；

​ 2️⃣求解大于k的num有多少种类

3，代码处理

package days;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _3375使数组的值全部为K的最少操作次数 {

    // 问题理解：转化为大于k的num有多少种，且不存在小于k的数据
    public int minOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int i = 0;
        for (; i < n; i++) {
            if (nums[i] < k) {
                return -1;
            } else if (nums[i] > k) {
                Set<Integer> set = new HashSet<>();
                for (int j = i; j < n; j++) {
                    set.add(nums[j]);
                }
                return set.size();
            }
        }
        return 0;
    }

    // 2ms 击败86.36%
    public int minOperations_optimize(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int i = 0;
        for (; i < n; i++) {
            if (nums[i] < k) {
                return -1;
            } else if (nums[i] > k) {
                int[] dp = new int[101];
                int cnt = 0;
                for (int j = i; j < n; j++) {
                    if (dp[nums[j]] == 0) {
                        cnt++;
                        dp[nums[j]] = 1;
                    }
                }
                return cnt;
            }
        }
        return 0;
    }

    // 1ms 击败100%
    // 无需进行排序，时间复杂度O（n），空间复杂度O（1）
    public int minOperations_optimize_v2(int[] nums, int k) {
        int[] dp = new int[101];
        int cnt = 0;
        for (int num : nums) {
            if (num < k) {
                return -1;
            } else if (num > k) {
                if (dp[num] == 0) {
                    cnt++;
                    dp[num] = 1;
                }
            }
        }
        return cnt;
    }
}