Easy

题目描述

给你一个整数数组 nums 和一个整数 k。

如果数组中所有严格大于 h 的值都相同，那么整数 h 被称为有效的。

例如，如果 nums = [10, 8, 10, 8]，那么 h = 9 是一个有效整数，因为所有 nums[i] > 9 都等于 10，但 5 不是有效整数。

你可以对 nums 执行以下操作：

  • 选择一个对当前 nums 中的值有效的整数 h。
  • 对于每个满足 nums[i] > h 的索引 i，将 nums[i] 设置为 h。

返回使 nums 中每个元素都等于 k 所需的最少操作次数。如果无法使所有元素都等于 k，返回 -1。

示例 1：

输入：nums = [5,2,5,4,5], k = 2
输出：2
解释：
可以按顺序使用有效整数 4 和 2 来执行操作。

示例 2：

输入：nums = [2,1,2], k = 2
输出：-1
解释：
无法使所有值都等于 2。

示例 3：

输入：nums = [9,7,5,3], k = 1
输出：4
解释：
可以按顺序使用有效整数 7、5、3 和 1 来执行操作。

约束：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

解题思路

解题思路

这道题的关键在于理解"有效整数"的定义和操作的本质。

分析操作过程：

  1. 每次操作选择一个有效的 h，将所有大于 h 的值设为 h
  2. 要使所有元素最终等于 k，我们需要逐步"降级"数组中的值
  3. 如果数组中存在小于 k 的元素，则无法通过操作使其增大到 k，返回 -1

关键观察：

  • 操作只能减小元素值，不能增大
  • 每次操作会消除数组中的一个不同的值（将其"合并"到更小的值）
  • 最优策略是从大到小逐步处理不同的值

算法步骤：

  1. 首先检查是否存在小于 k 的元素，如果有则返回 -1
  2. 使用集合去重，找出所有大于 k 的不同值
  3. 操作次数等于大于 k 的不同值的个数

举例说明：

  • nums = [5,2,5,4,5], k = 2：大于2的不同值有 {4, 5}，需要2次操作
  • 第一次：选择 h=4，将5都变成4，得到 [4,2,4,4,4]
  • 第二次：选择 h=2，将4都变成2，得到 [2,2,2,2,2]

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> uniqueValues;
        
        for (int num : nums) {
            if (num < k) {
                return -1;
            }
            if (num > k) {
                uniqueValues.insert(num);
            }
        }
        
        return uniqueValues.size();
    }
};

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

public class Solution {
    public int MinOperations(int[] nums, int k) {
        HashSet<int> uniqueValues = new HashSet<int>();
        
        foreach (int num in nums) {
            if (num < k) {
                return -1;
            }
            if (num > k) {
                uniqueValues.Add(num);
            }
        }
        
        return uniqueValues.Count;
    }
}

var minOperations = function(nums, k) {
    const uniqueValues = new Set();
    
    for (const num of nums) {
        if (num < k) {
            return -1;
        }
        if (num > k) {
            uniqueValues.add(num);
        }
    }
    
    return uniqueValues.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组一次，集合操作为 O(1)
空间复杂度O(n)最坏情况下集合存储所有不同的元素