当前位置: 首页 > 后端技术 > PHP

LeetcodePHP题解--D107453.MinimumMovestoEqualArrayElements

时间:2023-03-29 19:37:47 PHP

D107453.MinimumMovestoEqualArrayElements题目链接453.MinimumMovestoEqualArrayElements题目分析给定一个数组,对于数组中的N-1个Each数组每次递增1,它返回使所有元素值相等所需的最少步数。首先想到的想法是选择最小的n-1个元素在每一步添加。但很显然,每一步都对最大的数进行排序和剔除,一个一个地加起来,重新排序……很费时间。因此,我们要么寻找规律,要么简化寻找所需步骤数的方法。先分析比较简单的,再推广。1.1.1的情况直接return即可。因为所有元素都是一样的。以1.1.2为例,变成2.2.2只需要一步。以1.2.2为例,第一步是1.3.2;第二步2.3.3;第三步3.4.3;第四步是4.4.4。1.3.5、2.4.5、3.5.5、4.6.5、5.7.5、6.7.6、7.7.7。总共有6个步骤。这里感觉挺奇怪的,最后是7。我猜的规则是5+3-1,也就是sum减去最小值就是最终值,step是我猜是最终值减去最小值。但是,步数不遵循此规则。比如1.2.2的情况,最后的数字是4,但是步数不等于3。进一步分析这6步是怎么推导出来的。3-1=2、5-1=4、2+4=6。嗯?巧合吗?但是发现并没有满足1.2.2的情况。1.3.3、2.4.3、3.4.4、4.5.4、5.5.5。也是4步!3+3-1=5。不行,先加起来,再减:3+3+1-1-1,还是凑不上4,再减1,一共减了3个1。是元素个数1吗?于是我开始写代码测试所有元素的和减去n个最小值(n是数组的长度)。结果通过了。最终代码