5 line solution with comment


  • 2
    /*
    Intuitive solution might be making all the numbers the same as average.
    However that does not always work 
    [1,0,0,8,6]. average is 3, the total cost of making every number 3 is 16
    However if we were to make every number 1, cost is 14.
    
    Make every number the medium, instead of average would generate the smallest cost
    */
    
    public class Solution {
        public int minMoves2(int[] nums) {
            int sum = 0;
            Arrays.sort(nums);
            int medium = nums[nums.length / 2];
            for(int n : nums) sum += Math.abs(n - medium);
            return sum;
        }
    }````

  • 1
    Y

    Great solution. But I think it's not very convincing that the median is the best choice. I mean, your conclusion is correct but the proof is kinda weak, though.


  • 0

    @yuchenlin I agree, it is not very clear why the median is the correct solution. Here is the same solution but arrived at it differently. It might help you see why median is correct solution. Only real difference I'd say is that the median solution can be O(n) where as the sort requires O(N logN) but conceptually this one is the same.

    If you sort your array you will notice that you'll need to move elements from the ends inward to meet somewhere or perhaps one end can stay fixed and all the elements can move to it. You will always want to move one of the edge elements to their next neighbor according to the least cost of moving. This is determined by the gap between the edge and it's next neighbor multiplied by the number of elements that you need to move. As you repeat this process you will eventually move all the elements to one value. Total cost will be sum of cost at each step.

    The final value they meet at is the median, or left or right of the true median if there are an even number of elements. Think about when you are down to your final 2 values and you are going to move one to the other. Which one? The side with more elements stays fixed, and that side will necessarily have the median. You can expand this logic to see that the final location has the overall median value.


  • 0
    R

    we don't need to maintain the total number right ? if you make every number to 1 , you will discard some number


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.