Java(just like meeting point problem)


  • 46
    C
    public class Solution {
        public int minMoves2(int[] nums) {
            Arrays.sort(nums);
            int i = 0, j = nums.length-1;
            int count = 0;
            while(i < j){
                count += nums[j]-nums[i];
                i++;
                j--;
            }
            return count;
        }
    }

  • 0
    D

    Niiiiiiiiiiiiiiiiice!


  • 9
    V

    Need not to sort the entire array. Linear time QuickSelect is preferred here to compute median and solve this problem in O(n).


  • 1
    F

    Same idea:

    public class Solution {
        public int minMoves2(int[] nums) {
            Arrays.sort(nums);
            int res = 0, mid = nums.length/2;
            for(int i = 0; i < nums.length; i++){
                res += i > mid ? nums[i] - nums[mid] : nums[mid] - nums[i];
            }
            return res;
        }
    }
    

  • 2
    S

    Could you please explain why the solution works?


  • 1
    L

    Wait why does this work? It seems just out of the blue.


  • 1
    C

    @lekzeey
    @s961206
    you can think the number in the array is the position in 1d array. so, we need to find a position that all positions can reach and the sum is minimum.
    just like this problem in 1d
    https://leetcode.com/problems/best-meeting-point/
    Hope it helps


  • 20

    @lekzeey @s961206
    Suppose you have two endpoints A and B, when you want to find a point C that has minimum sum of distance between AC and BC, the point C will always between A and B. Draw a graph and you will understand it. Lets keep moving forward. After we locating the point C between A and B, we can define that
    dis(AC) = c - a; dis(CB) = b - c;
    sum = dis(AC) + dis(CB) = b - a.
    b - a will be a constant value, given specific b and a. Thus there will be no difference between points among A and B.

    In this problem, we set two boundaries, saying i and j, and we move the i and j to do the computation.

    Hope it helps.


  • 3

    The first time I actually used quick select to select the median element, which I thought would be faster than Arrays.sort() function. But it turned out that it's actually much slower than quick sort which is .sort() method. Anyone knows why?

    Arrays.sort(nums);
    int i = 0, j = nums.length - 1, res = 0;
    while (i < j) 
         res += nums[j--] - nums[i++];
    return res;
    

  • 1
    L

    @zhugejunwei I think Python used Timsort not quick sort. Also the .sort() method in python is written in C which should be much faster than your quick select in Python. I guess this is the reason.


  • 0

    Nice solution!
    Similar one, via streams:

    int minMoves2(int[] nums) {
      Arrays.sort(nums);
      int median = nums[nums.length >> 1];
      return Arrays.stream(nums).map(i -> Math.abs(median - i)).sum();
    }
    

  • 0
    A

    @fatalme - Similar logic but different way

    public int minMoves2(int[] nums) {
    if(nums == null || nums.length == 0)
    return 0;
    int sum = 0;
    Arrays.sort(nums);
    for(int i : nums)
    sum += Math.abs(i-nums[nums.length/2]); // distance of all from median
    return sum;
    }


  • 0
    Z
    This post is deleted!

Log in to reply
 

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