题目描述

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

样例

输入：nums = [5,2,5,4,5], k = 2

输出：2

解释：

依次选择合法整数 4 和 2，将数组全部变为 2。

输入：nums = [2,1,2], k = 2

输出：-1

解释：

没法将所有值变为 2。

输入：nums = [9,7,5,3], k = 1

输出：4

解释：

依次选择合法整数 7，5，3 和 1，将数组全部变为 1。

限制

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

算法

(思维题，哈希表) $O(n)$

1. 注意到，如果存在一个整数小于 $k$，则答案必是 $-1$。
2. 最少的操作次数一定是依次将最大的数字，次大的数字等按顺序往下调整，直到所有的数字都为 $k$。
3. 所以答案就是除了 $k$ 之外不同数字的个数。

时间复杂度

• 使用哈希表，遍历所有数字一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储出现的数字。

C++ 代码

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> seen;

        for (int x : nums) {
            if (x < k)
                return -1;

            if (x > k)
                seen.insert(x);
        }

        return seen.size();
    }
};