2023-08-28：用go語言編寫。給你一個正整數(shù)數(shù)組nums, 同時給你一個長度為 m 的整數(shù)數(shù)
2023-08-28：用go語言編寫。給你一個正整數(shù)數(shù)組nums, 同時給你一個長度為 m 的整數(shù)數(shù)組 queries。
第 i 個查詢中，你需要將 nums 中所有元素變成 queries[i] 。你可以執(zhí)行以下操作 任意 次：
將數(shù)組里一個元素 增大 或者 減小 1 。請你返回一個長度為 m 的數(shù)組 answer ，
其中 answer[i]是將 nums 中所有元素變成 queries[i] 的 最少 操作次數(shù)。
注意，每次查詢后，數(shù)組變回最開始的值。
輸入：nums = [3,1,6,8], queries = [1,5]。
輸出：[14,10]。
來自左程云。
答案2023-08-28：
大體過程如下：
1.定義?minOperations?函數(shù)，用于計算將?nums?中的元素轉(zhuǎn)換為?queries?中每個元素所需的最少操作次數(shù)。函數(shù)接受兩個參數(shù)：nums（正整數(shù)數(shù)組）和?queries（整數(shù)數(shù)組）。
2.獲取?nums?數(shù)組的長度，對?nums?進(jìn)行排序，并創(chuàng)建一個長度為?n+1?的?sum?數(shù)組，用于保存從?nums?累加得到的前綴和。
3.創(chuàng)建一個空的?ans?數(shù)組，用于存儲結(jié)果。
4.遍歷?queries?中的每個元素?v。
5.在?bs?函數(shù)中，使用二分查找找到?nums?中小于?v?的最右位置，并將結(jié)果賦給?less。
6.計算當(dāng)前查詢對應(yīng)的最少操作次數(shù)?curAns:
??初始化變量?
curAns?為?(less+1)*v - sum0(sum, 0, less)，表示將小于?v?的元素增加到?v?的操作次數(shù)。??在?
bs?函數(shù)中，使用二分查找找到?nums?中大于等于?v+1?的最左位置，并將結(jié)果賦給?more。??將?
curAns?更新為?curAns + sum0(sum, more+1, n-1) - (n-more-1)*v，表示將大于?v?的元素減小到?v?的操作次數(shù)。
7.將?curAns?添加到?ans?數(shù)組中。
8.返回得到的?ans?數(shù)組作為結(jié)果。
9.在?main?函數(shù)中，定義給定的?nums?和?queries。
10.調(diào)用?minOperations?函數(shù)，并將結(jié)果賦給?result。
11.打印結(jié)果?result。
總體的時間復(fù)雜度是 O(m*log(n))，其中 m 是?queries?的長度，n 是?nums?的長度。這是因為對于每個查詢，都需要使用二分查找來找到相應(yīng)的位置。
總體的空間復(fù)雜度是 O(n)，其中 n 是?nums?的長度。這是因為需要創(chuàng)建額外的數(shù)組?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++完整代碼如下：
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完整代碼如下：
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;
}
