How do I approach the 'Minimum Operations to Make All Array Elements Equal' problem?

Use binary search over the valid answer space to efficiently determine the minimum number of operations for each query.

Why should I sort the array for this problem?

Sorting the array ensures that binary search can be applied efficiently, allowing us to partition the array and calculate the number of operations more quickly.

What is the complexity of solving the 'Minimum Operations to Make All Array Elements Equal' problem?

The time complexity is dominated by O(n log n) for sorting the array, followed by O(log n) operations for each query, resulting in O(n log n + m log n) overall.

What is the optimal approach for calculating the number of operations for each query?

Using a combination of binary search, sorting, and prefix sums allows for efficient computation of the number of operations for each query.

How can GhostInterview help me prepare for this problem?

GhostInterview provides practice with binary search and array manipulation, helping you optimize your solution while ensuring it scales to large input sizes.

#2602

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

使数组元素全部相等的最少操作次数

给你一个正整数数组 nums 。同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作任意次：将数组里一个元素增大或者减小 1 。请你返回一个长度为 m 的数组 answer ，其中 an…

数组二分查找排序前缀和

题目描述

给你一个正整数数组 nums 。

同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作任意次：

将数组里一个元素增大或者减小 1 。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的最少操作次数。

注意，每次查询后，数组变回最开始的值。

示例 1：

输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：
- 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
- 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
- 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
第一个查询的总操作次数为 2 + 5 + 7 = 14 。
第二个查询，我们可以执行以下操作：
- 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
- 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
- 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
- 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。

示例 2：

输入：nums = [2,9,6,3], queries = [10]
输出：[20]
解释：我们可以将数组中所有元素都增大到 10 ，总操作次数为 8 + 1 + 4 + 7 = 20 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 10⁵
1 <= nums[i], queries[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 前缀和 + 二分查找

我们先将数组 $nums$ 进行排序，并计算出长度为 $n+1$ 的前缀和数组 $s$ ，其中 $s[i]$ 表示数组 $nums$ 中前 $i$ 个元素的和。

接下来，遍历每个查询 $queries[i]$ ，我们需要将所有大于 $queries[i]$ 的元素减小到 $queries[i]$ ，将所有小于 $queries[i]$ 的元素增大到 $queries[i]$ 。

我们可以通过二分查找找到数组 $nums$ 中第一个大于 $queries[i]$ 的元素的下标 $i$ ，则有 $n-i$ 个元素需要减小到 $queries[i]$ ，这些元素的和为 $s[n]-s[i]$ ，这些元素的和需要减去 $n-i$ 个 $queries[i]$ ，因此，这些元素减小到 $queries[i]$ 的总操作次数为 $s[n]-s[i]-(n-i)\times queries[i]$ 。

同理，我们可以找到数组 $nums$ 中第一个大于等于 $queries[i]$ 的元素的下标 $i$ ，则有 $i$ 个元素需要增大到 $queries[i]$ ，这些元素的和为 $s[i]$ ，因此，这些元素增大到 $queries[i]$ 的总操作次数为 $queries[i]\times i-s[i]$ 。

最后，将这两个总操作次数相加，即为将数组 $nums$ 中所有元素变成 $queries[i]$ 的最少操作次数，即 $ans[i]=s[n]-s[i]-(n-i)\times queries[i]+queries[i]\times i-s[i]$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        s = list(accumulate(nums, initial=0))
        ans = []
        for x in queries:
            i = bisect_left(nums, x + 1)
            t = s[-1] - s[i] - (len(nums) - i) * x
            i = bisect_left(nums, x)
            t += x * i - s[i]
            ans.append(t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate knowledge of binary search in a numerical setting and how it applies to optimizing the number of operations.
question_mark
Look for a solid understanding of prefix sums and sorting as methods to efficiently calculate the number of operations for each query.
question_mark
A strong candidate will discuss handling large input sizes and how the algorithm scales, particularly when dealing with up to 10^5 elements.

warning

常见陷阱

外企场景

error
Failing to consider the complexity of performing operations over large arrays and queries, which can lead to inefficient solutions.
error
Not utilizing binary search or prefix sums to optimize the search space and computation, leading to a time complexity that's too high.
error
Overcomplicating the solution by not recognizing the simplicity of binary search combined with sorted arrays for answering each query.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where you might need to handle queries with negative integers or zero, requiring additional handling.
arrow_right_alt
What if we need to handle arrays where elements can be changed by a fixed increment or decrement?
arrow_right_alt
You might want to explore what happens when all elements are already equal in the array before performing any operations.

help

常见问题

外企场景

继续练习

#2448 使数组相等的最小开销 #2389 和有限的最长子序列 #2271 毯子覆盖的最多白色砖块数