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

难度: Medium

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

Submission

运行时间: 297 ms

内存: 43.2 MB

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums = sorted(nums)
        ans = []
        n = len(nums)
        acc = [0 for i in range(n+1)]
        for i in range(n):
            acc[i+1] = acc[i] + nums[i]
        
        for q in queries:
            idx = bisect_right(nums, q)
            total = idx*q-acc[idx] + (acc[n]-acc[idx]) - (n-idx)*q
            ans.append(total)
        return ans

Explain

首先对数组 nums 进行排序，以方便后续快速计算。使用前缀和数组 acc 来存储 nums 的累积和，这样可以在常数时间内获取任意子数组的和。对于每个查询值 q，使用二分查找确定 q 在 nums 中的位置 idx，表示有 idx 个数小于或等于 q。接着计算将小于或等于 q 的所有数变为 q 的总操作数，以及大于 q 的所有数变为 q 的总操作数。这种方法避免了对每个元素逐一操作，提高了效率。

时间复杂度: O(n log n + m log n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums = sorted(nums)  # 对 nums 进行排序
        ans = []
        n = len(nums)
        acc = [0 for i in range(n+1)]  # 初始化前缀和数组
        for i in range(n):
            acc[i+1] = acc[i] + nums[i]  # 计算前缀和
        
        for q in queries:
            idx = bisect_right(nums, q)  # 使用二分查找确定 q 在 nums 中的位置
            # 计算将 nums 中所有小于等于 q 的元素变为 q 的操作次数
            total = idx * q - acc[idx] 
            # 计算将 nums 中所有大于 q 的元素变为 q 的操作次数
            total += (acc[n] - acc[idx]) - (n - idx) * q
            ans.append(total)
        return ans

Explore

在此算法中，使用前缀和数组可以显著提高计算效率。前缀和数组允许我们在常数时间内获取任意子数组的和，这对于多次查询尤其有用。如果直接对数组元素进行操作，每次查询时都需要遍历数组计算总和，这会导致时间复杂度显著增加。使用前缀和数组，我们可以避免重复计算同一区间的元素之和，从而优化整体性能。

二分查找通过在排序后的数组中迅速定位元素的位置，从而减少必要的计算次数。在本题中，二分查找用于确定查询值 q 在数组 nums 中的位置 idx，这表明有 idx 个数小于或等于 q。这种方法比线性搜索更有效，因为二分查找的时间复杂度为 O(log n)，而线性搜索的时间复杂度为 O(n)。这使得算法在处理大规模数据时更加高效。

对于表达式 `total = idx * q - acc[idx]`，这计算了将数组中所有小于等于 q 的元素变为 q 所需的总操作次数。这里，`idx * q` 是如果将所有小于等于 q 的 idx 个元素变为 q 所得到的总和，而 `acc[idx]` 是原始数组中这些元素的实际总和。两者之差即为需要增加的总量。对于表达式 `total += (acc[n] - acc[idx]) - (n - idx) * q`，这计算了将所有大于 q 的元素变为 q 所需的总操作次数。这里 `(acc[n] - acc[idx])` 是原数组中大于 q 的元素的总和，而 `(n - idx) * q` 是如果这些元素都变为 q 时的总和。两者之差即为需要减少的总量。

排序和使用前缀和数组的方法在大多数情况下都是有效的，但它们特别适用于需要重复查询的情况。排序一次的时间复杂度为 O(n log n)，而建立前缀和数组的时间复杂度为 O(n)。对每个查询的处理时间是 O(log n)。因此，这种方法在处理单次查询时可能不如某些专门的算法高效，但在需要执行大量查询的情况下，预处理的成本可以被多次查询所平摊，从而提高总体效率。在具有特别小或特别大的数据规模时，性能表现可能会受到物理内存和处理能力的限制。