This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic link

462. The minimum number of moves to make the array elements equal II

Topic describes

Given an array of non-empty integers, find the minimum number of moves required to make all the array elements equal, where each move adds or subtracts one of the selected elements by one. You can assume that the array is at most 10,000 long.

The test case

Input: [1, 2, 3]

Output: 2

Subject analysis

preface

When you are doing this problem, may be because there is no train of thought, and then go to the comment area to see, each problem solution a turn, will be full of question mark, “why? Why do they always say you have to use the median?” I don’t know why, but I solved it with the idea of median 😶

Let’s start with a small test sample

Give a sorted test example [0, 1, 2, 6, 8]

Through the observation of data, it can be known that the minimum number of movement of the first and last numbers 0 and 8 is to find any number between [0, 8], and their fixed number of movement is 8. If you try to find a number outside this interval to count the number of moves, such as -1, then 0 and 8 will have 10 moves

Similarly, if we move 1 and 6 for the minimum number of times, any number in [1, 6] will move fixed 5 times

And then you’re left with a middle number, 2, which is at least zero if you don’t move

That reference would be [0, 8] ∪ [1, 6] ∪ [2] = 2. The minimum number of moves they can take is 8+5+0 = 13

So we’re looking for the median, so we’re looking for an odd array, and we’re looking for an even array

Example: [0, 1, 2, 6]

1. Find a number at [0, 6] with a fixed minimum degree of 6

The middle number is selected as [0, 6] ∪ [1, 2] = [1, 2], that is, 1 or 2 is ok, and the minimum number of moves is 6+1 = 7

The topic answer

I figured it out in the last step and using the median is a good way to do it, so it’s easy to get the code out

  1. Sorts the given array
  2. Using double Pointers,leftPoint to theindex=0.rightPoint to theindex=nums.length-1
  3. Takes the absolute value difference between the numbers pointed to by the left and right Pointers
  4. The left and right Pointers move closer to the center
  5. Handles special cases where the left and right Pointers are centered
    1. Left and right pointer overlap
    2. Left and right pointer adjacent

Post code

var minMoves2 = function(nums) {
    nums.sort((a, b) = > a - b);
    let index = (nums.length - 1) / 2;
    let center = Math.floor((nums[Math.floor(index)] + nums[Math.ceil(index)])) / 2;
    return nums.reduce((a, b) = > a + Math.abs(b - center), 0);
};
Copy the code