What is the minimum operations approach for this array scanning plus hash lookup problem?

Scan the array to count frequencies, identify the highest valid integer at each step, reduce numbers, and repeat until all values reach k or return -1 if impossible.

Why do we return -1 in some cases?

If nums contains values less than k or elements cannot be aligned using valid reductions, the operations cannot succeed, so -1 signals impossibility.

How do hash tables help in this problem?

Hash tables efficiently track frequencies of numbers, allowing quick identification of valid integers for each reduction step.

Can we perform operations in any order?

No, operations must reduce numbers from the highest valid integer down to k to ensure the minimum number of steps.

Does this method work for arrays of any size up to the constraint?

Yes, the approach scales linearly with n and handles arrays up to length 100, matching the problem constraints.

#3375

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 nums 和一个整数 k 。如果一个数组中所有严格大于 h 的整数值都相等，那么我们称整数 h 是合法的。比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个合法整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 …

数组哈希表

题目描述

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

lightbulb

解题思路

方法一：哈希表

根据题目描述，我们每次可以选择当前数组中的次大值作为合法整数 $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}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

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)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is scanned once and hash lookups are O(1). Space complexity is O(n) to store frequency counts for each unique number in nums.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Are you correctly identifying the valid integer h at each step?
question_mark
Can you explain why some sequences cannot reach k and must return -1?
question_mark
How do you optimize the scanning to avoid redundant checks for already reduced numbers?

warning

常见陷阱

外企场景

error
Ignoring elements less than k which make the task impossible.
error
Failing to update frequencies correctly after each reduction.
error
Confusing the order of operations when multiple valid integers exist.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find minimum operations when multiple arrays are given and each needs to reach its own target k.
arrow_right_alt
Modify the problem to allow decreasing numbers to any smaller integer instead of only valid integers.
arrow_right_alt
Calculate maximum operations instead of minimum using the same pattern of array scanning and hash lookup.

help

常见问题

外企场景

继续练习

#3378 统计最小公倍数图中的连通块数目 #3371 识别数组中的最大异常值 #3381 长度可被 K 整除的子数组的最大元素和