每日一题-使数组的值全部为 K 的最少操作次数🟢

LeetCode 每日一题题解

2025年4月9日 00:00

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

去重计算

LeetCode 每日一题题解

作者 admiring-meninskyuli

2024年12月8日 10:46

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

[TOC]

思路

按题意去重计数计算

Code

执行用时分布68ms击败100.00%；消耗内存分布16.89MB击败100.00%

###Python3

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        if min(nums) < k: return -1
        return len(set(nums + [k])) - 1

LeetCode 每日一题题解
本质是计算不同元素个数（Python/Java/C++/Go/JS/Rust）endlesscheng
2024年12月8日 09:11

本质是计算不同元素个数（Python/Java/C++/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2024年12月8日 09:11

思考框架

理解操作在做什么。
把 $\textit{nums}$ 中的数都变成一样的，能变成哪些数？
如何最小化操作次数？

操作在做什么

题目说「选择一个整数 $h$」，哪些 $h$ 是可以选的？

根据「合法」的定义，$h$ 不能低于 $\textit{nums}$ 的次大值。比如 $\textit{nums}=[5,2,5,4,5]$，$h$ 不能小于次大值 $4$，否则大于 $h$ 的数不都相等。

所以操作只能改变大于次大值的数，也就是最大值。

能变成哪些数

要让所有数都变成 $k$，前提条件是所有数都变成一样的。那么，能变成哪些数呢？

仍然以 $\textit{nums}=[5,2,5,4,5]$ 为例。选择 $h=4$，可以把最大值 $5$ 改成次大值 $4$。修改后 $\textit{nums}=[4,2,4,4,4]$，有更多的数都相同。并且修改后，原来的次大值 $4$ 就变成最大值了。下一次操作，我们就可以选择更小的 $h$，把更多的数都变成一样的。

选择 $h=2$，可以把最大值 $4$ 改成次大值 $2$。修改后 $\textit{nums}=[2,2,2,2,2]$，所有数都相同。

如果想继续改成比 $2$ 小的数，比如 $0$，选择 $h=0$ 即可。

所以，$\textit{nums}$ 中的数可以都变成任意 $\le \min(\textit{nums})$ 的数。

最小化操作次数

为了最小化操作次数，每次选 $h$ 为次大值是最优的。贪心地想，能一步到达次大值，没必要分好几步。

分类讨论：

如果 $k > \min(nums)$，无法满足要求，返回 $-1$。
如果 $k = \min(nums)$，操作次数为 $\textit{nums}$ 中的不同元素个数减一。比如 $[5,2,5,4,5]\to [4,2,4,4,4]\to [2,2,2,2,2]$，最大值 $5\to 4\to 2$，用了 $2$ 次操作。
如果 $k < \min(nums)$，操作次数为 $\textit{nums}$ 中的不同元素个数。因为都变成 $\min(nums)$ 后，还需要再操作一次，才能都变成 $k$。

###py

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        mn = min(nums)
        if k > mn:
            return -1
        return len(set(nums)) - (k == mn)

###java

class Solution {
    public int minOperations(int[] nums, int k) {
        int min = Arrays.stream(nums).min().getAsInt();
        if (k > min) {
            return -1;
        }
        int distinctCount = (int) Arrays.stream(nums).distinct().count();
        return distinctCount - (k == min ? 1 : 0);
    }
}

###cpp

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int mn = ranges::min(nums);
        if (k > mn) {
            return -1;
        }
        unordered_set<int> st(nums.begin(), nums.end());
        return st.size() - (k == mn);
    }
};

###go

func minOperations(nums []int, k int) int {
    mn := slices.Min(nums)
    if k > mn {
        return -1
    }

    set := map[int]struct{}{}
    for _, x := range nums {
        set[x] = struct{}{}
    }
    if k == mn {
        return len(set) - 1
    }
    return len(set)
}

###js

var minOperations = function(nums, k) {
    const min = Math.min(...nums);
    if (k > min) {
        return -1;
    }
    return new Set(nums).size - (k === min ? 1 : 0);
};

###rust

use std::collections::HashSet;

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let min = *nums.iter().min().unwrap();
        if k > min {
            return -1;
        }
        let set = nums.into_iter().collect::<HashSet<_>>();
        set.len() as i32 - if k == min { 1 } else { 0 }
    }
}