I just guessed it should be the median point but I don't have a formal proof yet.
Convert the problem to a math problem:
f(x) = |x - x_1| +|x - x_2| + |x - x_3| + ... + |x - x_n|
We know |x - a| + |x - b| >= |a - b| from high school math
f(x) > = |x_1 - xn| + |x_2 - x_n-1| + ... + |x_k - x_k+1|
Assume x_m = median,
Then x_i < x_m when i < m and x_i >= x_m when i >= m.
f(x_m) = (x_m - x_1) + (x_m - x_2) + ... + (x_m - x_m+1) - (x_m+2 - xm+3) - ... - (x_n-1 - x_n)
f(x_m) = |x_1 - xn| + |x_2 - x_n-1| + ... + |x_k - x_k+1|
Then when x = x_m, f(x) reaches minimum value.
class Solution(object): def minMoves2(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() mid = nums[len(nums) / 2] return sum(abs(num - mid) for num in nums)
I guess you can argue that the built-in sorting method is optimized to perform closer to average O(n), but I still think in an interview context a built-in sorting method would be considered resorting to a O(nlogn) complexity on average.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.