public class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length1;
int count = 0;
while(i < j){
count += nums[j]nums[i];
i++;
j;
}
return count;
}
}
Java(just like meeting point problem)

@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/bestmeetingpoint/
Hope it helps

@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.

The first time I actually used
quick select
to select the median element, which I thought would be faster thanArrays.sort()
function. But it turned out that it's actually much slower thanquick 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;

@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.

@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(inums[nums.length/2]); // distance of all from median
return sum;
}