使数组元素全部相等的最少操作次数
难度:
标签:
题目描述
You are given an array nums consisting of positive integers.
You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:
- Increase or decrease an element of the array by
1.
Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].
Note that after each query the array is reset to its original state.
Example 1:
Input: nums = [3,1,6,8], queries = [1,5] Output: [14,10] Explanation: For the first query we can do the following operations: - Decrease nums[0] 2 times, so that nums = [1,1,6,8]. - Decrease nums[2] 5 times, so that nums = [1,1,1,8]. - Decrease nums[3] 7 times, so that nums = [1,1,1,1]. So the total number of operations for the first query is 2 + 5 + 7 = 14. For the second query we can do the following operations: - Increase nums[0] 2 times, so that nums = [5,1,6,8]. - Increase nums[1] 4 times, so that nums = [5,5,6,8]. - Decrease nums[2] 1 time, so that nums = [5,5,5,8]. - Decrease nums[3] 3 times, so that nums = [5,5,5,5]. So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.
Example 2:
Input: nums = [2,9,6,3], queries = [10] Output: [20] Explanation: We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.
Constraints:
n == nums.lengthm == queries.length1 <= n, m <= 1051 <= nums[i], queries[i] <= 109
代码结果
运行时间: 297 ms, 内存: 43.2 MB
// Java Stream solution with detailed comments
// This solution uses Java Streams to perform the same calculation in a more functional style.
import java.util.Arrays;
public class Solution {
public int[] minOperations(int[] nums, int[] queries) {
return Arrays.stream(queries)
.map(query -> Arrays.stream(nums)
// For each query, calculate the total operations needed
.map(num -> Math.abs(num - query))
.sum())
.toArray();
}
}
解释
方法:
首先对数组 nums 进行排序，以方便后续快速计算。使用前缀和数组 acc 来存储 nums 的累积和，这样可以在常数时间内获取任意子数组的和。对于每个查询值 q，使用二分查找确定 q 在 nums 中的位置 idx，表示有 idx 个数小于或等于 q。接着计算将小于或等于 q 的所有数变为 q 的总操作数，以及大于 q 的所有数变为 q 的总操作数。这种方法避免了对每个元素逐一操作，提高了效率。
时间复杂度:
O(n log n + m log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，你为什么选择使用前缀和数组来辅助计算，而不是直接对数组元素进行操作？
▷🦆
二分查找是如何帮助确定查询值在数组中的位置，从而减少计算的总次数的？
▷🦆
对于每个查询，计算总操作数的部分`total = idx * q - acc[idx]`和`total += (acc[n] - acc[idx]) - (n - idx) * q`具体是如何工作的？可以详细解释这两个表达式吗？
▷🦆
排序和使用前缀和数组的方法是否适用于所有大小的数组，还是只针对特定大小或特性的数组最有效？
▷