D107 453. Minimum Moves to Equal Array Elements

Topic link

453. Minimum Moves to Equal Array Elements

Subject analysis

Given an array, incrementing each n-1 array by 1 returns the minimum number of steps required to make all elements equal.

Train of thought

So the first thing that comes to mind is to take the smallest n minus 1 element at each step. But obviously, we sort each step to exclude the largest numbers, add them up, and sort them again… It’s time consuming. So we need to find patterns and simplify the way to figure out the number of steps we need.

Let’s do the simpler ones first, and then generalize.

In the case of 1.1.1, return directly. Because all the elements are the same. In the case of 1.1.2, it only takes one step to become 2.2.2. In the case of 1.2.2, the first step is 1.3.2; The second step is 2.3.3; The third step is 3.4.3; Step 4 is 4.4.4.

1.3.5, 2.4.5, 3.5.5, 4.6.5, 5.7.5, 6.7.6, 7.7.7. A total of six steps. This is kind of weird. It ends up being 7. I guess the rule is 5 plus 3 minus 1, which is the sum minus the minimum is the final value, and the step is I guess the final value minus the minimum.

However, the number of steps does not conform to this rule. For example, in the case of 1.2.2, the final value is 4, but the number of steps is not equal to 3.

Further analysis of how the 6 steps are obtained. 3 minus 1 is 2,5 minus 1 is 4, 2 plus 4 is 6. Aye? As it happens? However, the case of 1.2.2 was found to be inconsistent.

1.3.3, 2.4.3, 3.4.4, 4.5.4, 5.5.5. Also 4 steps! 3 + 3-1 = 5. No, let’s add it all up and subtract it: 3+3+1-1-1, but you still can’t make a 4, so subtract 1. We’re going to subtract three ones. Does it have to be one? So I start writing code that tests the sum of all elements minus n minima (n is the length of the array).

And it passed.

The final code

      
class Solution {

    / * * *@param Integer[] $nums
     * @return Integer
     */
    function minMoves($nums) {
        $min = min($nums);
        returnarray_sum($nums) - count($nums) * $min; }}Copy the code

The code only beat 60%! I want to… Min, array_sum, count… So instead:

      
class Solution {

    / * * *@param Integer[] $nums
     * @return Integer
     */
    function minMoves($nums) {
        $min = 9999999999999999999;
        $total = 0;
        $amount = 0;
        foreach($nums as $n){
            if($n<$min){
                $min = $n;
            }
            $total += $n;
            $amount++;
        }
        return$total - $amount * $min; }}Copy the code

That’s over 80% of the code! It’s not 100%, but it’s a little more efficient, right?

If you find this article useful, you are welcome to subsidize it with love.