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

来源第 145 场双周赛 Q1难度简单分数1382

题目描述

给你一个整数数组 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

解法

方法一：哈希表

思考

每次把所有大于当前次大值 \(h\) 的数改成 \(h\)，最终要变成 \(k\)。操作只会变小，故若存在小于 \(k\) 的数则无解。

每次操作恰好消灭当前最大值这一档。不同的大于 \(k\) 的值各需一次操作；若最小值已经是 \(k\)，则这一档不必再改。

因此用集合去重后，答案为不同值个数减去 \([\textit{mi}=k]\)。

根据题目描述，我们每次可以选择当前数组中的次大值作为合法整数 \(h\)，将所有大于 \(h\) 的数都变为 \(h\)，这样可以使得操作次数最少。另外，由于操作会使得数字变小，因此，如果当前数组中存在小于 \(k\) 的数，那么我们就无法将所有数都变为 \(k\)，直接返回 -1 即可。

我们遍历数组 \(\textit{nums}\)，对于当前的数 \(x\)，如果 \(x < k\)，直接返回 -1；否则，我们将 \(x\) 加入哈希表中，并且更新当前数组中的最小值 \(\textit{mi}\)。最后，我们返回哈希表的大小减去 1（如果 \(\textit{mi} = k\)，则需要减去 1）。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScriptJavaScriptRust

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        s = set()
        mi = inf
        for x in nums:
            if x < k:
                return -1
            mi = min(mi, x)
            s.add(x)
        return len(s) - int(k == mi)

class Solution {
    public int minOperations(int[] nums, int k) {
        Set<Integer> s = new HashSet<>();
        int mi = 1 << 30;
        for (int x : nums) {
            if (x < k) {
                return -1;
            }
            mi = Math.min(mi, x);
            s.add(x);
        }
        return s.size() - (mi == k ? 1 : 0);
    }
}

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> s;
        int mi = INT_MAX;
        for (int x : nums) {
            if (x < k) {
                return -1;
            }
            mi = min(mi, x);
            s.insert(x);
        }
        return s.size() - (mi == k);
    }
};

func minOperations(nums []int, k int) int {
    mi := 1 << 30
    s := map[int]bool{}
    for _, x := range nums {
        if x < k {
            return -1
        }
        s[x] = true
        mi = min(mi, x)
    }
    if mi == k {
        return len(s) - 1
    }
    return len(s)
}

function minOperations(nums: number[], k: number): number {
    const s = new Set<number>([k]);
    for (const x of nums) {
        if (x < k) return -1;
        s.add(x);
    }
    return s.size - 1;
}

function minOperations(nums, k) {
    const s = new Set([k]);
    for (const x of nums) {
        if (x < k) return -1;
        s.add(x);
    }
    return s.size - 1;
}

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashSet;

        let mut s = HashSet::new();
        let mut mi = i32::MAX;

        for &x in &nums {
            if x < k {
                return -1;
            }
            s.insert(x);
            mi = mi.min(x);
        }

        (s.len() as i32) - if mi == k { 1 } else { 0 }
    }
}

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

题目描述

解法

方法一：哈希表

评论