526互联

2023-08-28：用go语言编写。给你一个正整数数组nums, 同时给你一个长度为 m 的整数数组 queries。 第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。

发布时间 2023-08-28 16:19:58作者: 福大大架构师每日一题

2023-08-28：用go语言编写。给你一个正整数数组nums, 同时给你一个长度为 m 的整数数组 queries。

第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：

将数组里一个元素 增大 或者 减小 1 。请你返回一个长度为 m 的数组 answer ，

其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

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

输入：nums = [3,1,6,8], queries = [1,5]。

输出：[14,10]。

来自左程云。

答案2023-08-28：

大体过程如下：

1.定义 minOperations 函数，用于计算将 nums 中的元素转换为 queries 中每个元素所需的最少操作次数。函数接受两个参数：nums（正整数数组）和 queries（整数数组）。

2.获取 nums 数组的长度，对 nums 进行排序，并创建一个长度为 n+1 的 sum 数组，用于保存从 nums 累加得到的前缀和。

3.创建一个空的 ans 数组，用于存储结果。

4.遍历 queries 中的每个元素 v。

5.在 bs 函数中，使用二分查找找到 nums 中小于 v 的最右位置，并将结果赋给 less。

6.计算当前查询对应的最少操作次数 curAns:

  • 初始化变量 curAns 为 (less+1)*v - sum0(sum, 0, less)，表示将小于 v 的元素增加到 v 的操作次数。

  • 在 bs 函数中，使用二分查找找到 nums 中大于等于 v+1 的最左位置，并将结果赋给 more。

  • 将 curAns 更新为 curAns + sum0(sum, more+1, n-1) - (n-more-1)*v，表示将大于 v 的元素减小到 v 的操作次数。

7.将 curAns 添加到 ans 数组中。

8.返回得到的 ans 数组作为结果。

9.在 main 函数中，定义给定的 nums 和 queries。

10.调用 minOperations 函数，并将结果赋给 result。

11.打印结果 result。

总体的时间复杂度是 O(m*log(n))，其中 m 是 queries 的长度，n 是 nums 的长度。这是因为对于每个查询，都需要使用二分查找来找到相应的位置。

总体的空间复杂度是 O(n)，其中 n 是 nums 的长度。这是因为需要创建额外的数组 sum 来保存前缀和。

go完整代码如下：

package main

import (
	"fmt"
	"sort"
)

func minOperations(nums []int, queries []int) []int {
	n := len(nums)
	sort.Ints(nums)
	sum := make([]int, n+1)
	for i := 0; i < n; i++ {
		sum[i+1] = sum[i] + int(nums[i])
	}
	ans := make([]int, 0)
	var less, more, curAns int
	for _, v := range queries {
		less = bs(nums, v)
		curAns = (less+1)*int(v) - sum0(sum, 0, int(less))
		more = bs(nums, v+1)
		curAns += sum0(sum, more+1, n-1) - int(n-more-1)*int(v)
		ans = append(ans, curAns)
	}
	return ans
}

// 查找 <v 最右的位置
// 没有返回-1
func bs(nums []int, v int) int {
	l := 0
	r := len(nums) - 1
	var m, ans int = -1, -1
	for l <= r {
		m = int((l + r) / 2)
		if nums[m] < v {
			ans = m
			l = int(m + 1)
		} else {
			r = int(m - 1)
		}
	}
	return ans
}

func sum0(sum []int, l, r int) int {
	if l > r {
		return 0
	}
	return sum[r+1] - sum[l]
}

func main() {
	nums := []int{3, 1, 6, 8}
	queries := []int{1, 5}
	result := minOperations(nums, queries)
	fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下：

fn min_operations(nums: Vec<i32>, queries: Vec<i32>) -> Vec<i64> {
    let mut nums = nums.clone();
    nums.sort();

    let n = nums.len() as i32;
    let mut sum = vec![0; n as usize + 1];
    for i in 0..n {
        sum[i as usize + 1] = sum[i as usize] + nums[i as usize] as i64;
    }

    let mut ans = Vec::new();
    for v in queries {
        let less = bs(&nums, v);
        let mut cur_ans = (less + 1) as i64 * v as i64 - sum0(&sum, 0, less);
        let more = bs(&nums, v + 1);
        cur_ans += sum0(&sum, more + 1, n - 1) - (n - more - 1) as i64 * v as i64;
        ans.push(cur_ans);
    }

    ans
}

fn bs(nums: &Vec<i32>, v: i32) -> i32 {
    let mut l = 0;
    let mut r = nums.len() as i32 - 1;
    let mut ans = -1;

    while l <= r {
        let m = (l + r) / 2;
        if nums[m as usize] < v {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    ans
}

fn sum0(sum: &Vec<i64>, l: i32, r: i32) -> i64 {
    if l > r {
        0
    } else {
        sum[r as usize + 1] - sum[l as usize]
    }
}

fn main() {
    let nums = vec![3, 1, 6, 8];
    let queries = vec![1, 5];

    let result = min_operations(nums, queries);
    println!("{:?}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int bs(vector<int>& nums, int v) {
    int l = 0;
    int r = nums.size() - 1;
    int m, ans = -1;
    while (l <= r) {
        m = (l + r) / 2;
        if (nums[m] < v) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

long long sum0(vector<long long>& sum, int l, int r) {
    return l > r ? 0 : (sum[r + 1] - sum[l]);
}

vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
    int n = nums.size();
    sort(nums.begin(), nums.end());

    vector<long long> sum(n + 1, 0);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }

    vector<long long> ans;
    int less, more;
    long long curAns;
    for (int v : queries) {
        less = bs(nums, v);
        curAns = (long long)(less + 1) * v - sum0(sum, 0, less);
        more = bs(nums, v + 1);
        curAns += sum0(sum, more + 1, n - 1) - (long long)(n - more - 1) * v;
        ans.push_back(curAns);
    }
    return ans;
}

int main() {
    vector<int> nums = { 3, 1, 6, 8 };
    vector<int> queries = { 1, 5 };

    vector<long long> result = minOperations(nums, queries);

    for (long long ans : result) {
        cout << ans << " ";
    }
    cout << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int* nums, int numsSize, int v) {
    int l = 0;
    int r = numsSize - 1;
    int m, ans = -1;
    while (l <= r) {
        m = (l + r) / 2;
        if (nums[m] < v) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

long long sum(long long* sumArray, int l, int r) {
    return l > r ? 0 : (sumArray[r + 1] - sumArray[l]);
}

int cmpfunc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long* minOperations(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    int n = numsSize;
    qsort(nums, n, sizeof(int), cmpfunc);
    long long* sumArray = (long long*)malloc((n + 1) * sizeof(long long));
    sumArray[0] = 0;
    for (int i = 0; i < n; i++) {
        sumArray[i + 1] = sumArray[i] + nums[i];
    }

    long long* ans = (long long*)malloc(queriesSize * sizeof(long long));

    int less, more;
    long long curAns;
    for (int i = 0; i < queriesSize; i++) {
        int v = queries[i];
        less = binarySearch(nums, n, v);
        curAns = (long long)(less + 1) * v - sum(sumArray, 0, less);
        more = binarySearch(nums, n, v + 1);
        curAns += sum(sumArray, more + 1, n - 1) - (long long)(n - more - 1) * v;
        ans[i] = curAns;
    }

    *returnSize = queriesSize;
    return ans;
}

int main() {
    int nums[] = { 3, 1, 6, 8 };
    int queries[] = { 1, 5 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int queriesSize = sizeof(queries) / sizeof(queries[0]);
    int returnSize;

    long long* result = minOperations(nums, numsSize, queries, queriesSize, &returnSize);

    printf("Result: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%lld ", result[i]);
    }
    printf("\n");

    free(result);
    return 0;
}

在这里插入图片描述