LeetCode 2602. 使数组元素全部相等的最少操作次数【排序,前缀和,二分】中等

本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你一个正整数数组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]。 第一个查询的总操作次数为25714。 第二个查询我们可以执行以下操作-将 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]。 第二个查询的总操作次数为241310。示例 2输入nums[2,9,6,3],queries[10]输出[20]解释我们可以将数组中所有元素都增大到10总操作次数为814720。提示n nums.lengthm queries.length1 n, m 10^51 nums[i], queries[i] 10^9方法 排序前缀和二分classSolution{publicListLongminOperations(int[]nums,int[]queries){Arrays.sort(nums);intnnums.length;long[]sumnewlong[n1];// 前缀和for(inti0;in;i){sum[i1]sum[i]nums[i];}ListLongansnewArrayList(queries.length);// 预分配空间for(intq:queries){intjlowerBound(nums,q);longleft(long)q*j-sum[j];// 蓝色面积longrightsum[n]-sum[j]-(long)q*(n-j);// 绿色面积ans.add(leftright);}returnans;}// 见 https://www.bilibili.com/video/BV1AP41137w7/privateintlowerBound(int[]nums,inttarget){intleft-1;intrightnums.length;// 开区间 (left, right)while(left1right){// 区间不为空// 循环不变量// nums[left] target// nums[right] targetintmidleft(right-left)/2;if(nums[mid]target){leftmid;// 范围缩小到 (mid, right)}else{rightmid;// 范围缩小到 (left, mid)}}returnright;}}classSolution{public:vectorlonglongminOperations(vectorintnums,vectorintqueries){ranges::sort(nums);intnnums.size();vectorlonglongsum(n1);// 前缀和for(inti0;in;i){sum[i1]sum[i]nums[i];}intmqueries.size();vectorlonglongans(m);for(inti0;im;i){intqqueries[i];longlongjranges::lower_bound(nums,q)-nums.begin();longlongleftq*j-sum[j];// 蓝色面积longlongrightsum[n]-sum[j]-q*(n-j);// 绿色面积ans[i]leftright;}returnans;}};classSolution:defminOperations(self,nums:List[int],queries:List[int])-List[int]:nlen(nums)nums.sort()slist(accumulate(nums,initial0))# 前缀和ans[]forqinqueries:jbisect_left(nums,q)leftq*j-s[j]# 蓝色面积rights[n]-s[j]-q*(n-j)# 绿色面积ans.append(leftright)returnansfuncminOperations(nums,queries[]int)[]int64{n:len(nums)slices.Sort(nums)sum:make([]int,n1)// 前缀和fori,x:rangenums{sum[i1]sum[i]x}ans:make([]int64,len(queries))fori,q:rangequeries{j:sort.SearchInts(nums,q)left:q*j-sum[j]// 蓝色面积right:sum[n]-sum[j]-q*(n-j)// 绿色面积ans[i]int64(leftright)}returnans}复杂度分析时间复杂度O ( ( n q ) l o g n ) O((nq)logn)O((nq)logn)其中n nn为n u m s numsnums的长度q qq为q u e r i e s queriesqueries的长度。空间复杂度O ( n ) O(n)O(n)。返回值不计入。