社区讨论LinuxDo 最新
各位大佬觉得这个算法的解释写的怎么样,能看懂吗,可以给些建议吗
大家觉得这个怎么样,前面的都是我自己写的,后面实在不知道怎么组织语言了,叫ai帮我写了后面的文字解释,这个能发在leetcode吗,大家看得懂吗 2333.最小差值平方和 题目大致意思 给定两个数组,这两个数组里面的任意数字一次可以+1或者-1,数组1最多加减k1次,数组2最多加减k2次,然后计算这两个数组同一个index 位置的差值的平方,将两个数组的所有位置的差值的平方加起来,求它的最小值 大致思路 首先能想到的就是把两个数组里面的数分别拿出来相减然后取绝对值,然后进行排序,k1和k2可以直接加起来当做全部的…
内容摘要
作者:#路小雨
板块:#搞七捻三
大家觉得这个怎么样,前面的都是我自己写的,后面实在不知道怎么组织语言了,叫ai帮我写了后面的文字解释,这个能发在leetcode吗,大家看得懂吗
2333.最小差值平方和
题目大致意思
给定两个数组,这两个数组里面的任意数字一次可以+1或者-1,数组1最多加减k1次,数组2最多加减k2次,然后计算这两个数组同一个index 位置的差值的平方,将两个数组的所有位置的差值的平方加起来,求它的最小值
大致思路
首先能想到的就是把两个数组里面的数分别拿出来相减然后取绝对值,然后进行排序,k1和k2可以直接加起来当做全部的次数,下面用k表示所有的次数;因为绝对值的加减无论是两个数组的那两个进行加减都能达到-1的效果,从最高位开始依次开始-1 ,即慢慢的让数组之间的差值变小,但是存在问题,需要for循环多次,算出来时间已经超标了;这里就可以开始优化了,没必要每次只-1 ,
假设[2,3,6,8,10] 是已经计算好的、进行排序的并且还没经过减少k次的两个数组的差值,这里再假设k=7
首先就是10-2 得到[2,3,6,8,8] ,此处k=2 ,在此处不需要再每个数进行减少,而是分层减少,此时的后两个8 就可以都同时进行减少,以此减少循环的次数
再就是8-2 8-2 得到[2,3,6,6,6] ,此处k=4
这时k还剩1 ,无论拿哪个6进行-1就无所谓了,得到的就是[2,3,5,6,6] 这样的数组
但这时问题又来了,这个问题需要在计算好两个数组差值并进行排序后然后才开始,排序消耗的开销无法避免,而且需要数组一个元素一个元素的遍历过去,整个的时间复杂度会很复杂,像在[2,3,6,8,8] 时这里的8有两个,分层减少也需要进行两次,那如果极限一点
假设存在[1,2,…,2],这里的2有n个那就需要进行n次循环以此进行减小,这时的时间开销就很大了,对于这种情况就需要进行优化了,这里存在的规律就是相同的数需要进行相同用到减少 ,最后得到的数组需要求整个的平方和,如果是相同的数的话,只需要计算这个数有多少然后乘以这个数的平方就可以,以上面的[1,2,…,2] 为例,
资讯来源
LinuxDo