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

链接：2602.使数组元素全部相等的最少操作次数
难度：Medium
标签：数组、二分查找、前缀和、排序
简介：给你一个正整数数组 nums 。请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

题解 1 - rust

• 编辑时间：2023-03-26
• 执行用时：60ms
• 内存消耗：5MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_operations(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i64> {
        nums.sort();
        let mut sums: Vec<i64> = vec![0; 1];
        for num in &nums {
            sums.push(*sums.last().unwrap() + *num as i64);
        }
        let mut res = vec![];
        for q in queries {
            let q = q as usize;
            let (mut l, mut r) = (0, nums.len());
            while l < r {
                let m = (l + r) / 2;
                if nums[m] >= q as i32 {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            if l == 0 || r == nums.len() {
                res.push((*sums.last().unwrap() - (q * nums.len()) as i64).abs());
            } else {
                let (nl, nr) = (sums[l] - sums[0], sums[nums.len()] - sums[l]);
                let (l, q) = (l as i64, q as i64);
                let (vl, vr) = (l * q - nl, nr - (nums.len() as i64 - l) * q);
                res.push(vl + vr);
            }
        }
        res
    }
}

题解 2 - python

• 编辑时间：2023-03-26
• 执行用时：792ms
• 内存消耗：44.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        sums = [0]
        for num in nums:
            sums.append(sums[-1] + num)
        res = []
        for q in queries:
            l, r = 0, len(nums)
            while l < r:
                m = (l+r)//2
                if nums[m] >= q:
                    r = m
                else:
                    l = m+1
            if l == 0 or r == len(nums):
                res.append(abs(sums[-1] - q * len(nums)))
            else:
                nl, nr = sums[l] - sums[0], sums[nums.size()] - sums[l]
                vl, vr = l * q - nl, nr - (nums.size() - l) * q
                res.append(vl+vr)
        return res

题解 3 - cpp

• 编辑时间：2023-03-26
• 执行用时：244ms
• 内存消耗：82.5MB
• 编程语言：cpp
• 解法介绍：排序后求前缀和，小值趋近大，大值趋近小。

class Solution {
public:
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        vector<long long> sums(1, 0);
        for (auto &num: nums) sums.push_back(sums.back() + num);
        vector<long long> res;
        for (auto &qv : queries) {
            long long q = qv; 
            int l = 0, r = nums.size();
            while (l < r) {
                int m = (l + r) / 2;
                if (nums[m] >= q) r = m;
                else l = m + 1;
            }
            if (l == 0 || r == nums.size()) 
                res.push_back(fabs(sums.back() - q * (long long)nums.size()));
            else {
                long long nl = sums[l] - sums[0], nr = sums[nums.size()] - sums[l],
                          vl = l * q - nl, vr = nr - (nums.size() - l) * q;
                res.push_back(vl + vr);
            }
        }
        return res;
    }
};