462.Minimum Moves to Equal Array Elements II

Tags: [sort], [median]

Link: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/?tab=Solutions

Given anon-emptyinteger array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array's length is at most 10,000.

Example:

Input:

[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]

Solution:

import sys

class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        # get the median number
        nums_len = len(nums)
        nums.sort()

        if nums_len % 2 == 1:
            # the number of elements is odd
            target_num = nums[nums_len / 2]
            return sum([abs(target_num - x) for x in nums])
        else:
            # the number of elements is even
            target_num_1 = nums[nums_len / 2 - 1]
            target_num_2 = nums[nums_len / 2]
            return min(sum([abs(target_num_1 - x) for x in nums]),
                       sum([abs(target_num_2 - x) for x in nums]))

Revelation:

• There is T = O(nlgn) between T = O(n^2) and T = O(n).
• If we have already solved the problem in T = O(n^2), and we know we still can optimize the algorithm, we should not think the next step is T = O(n), which probably means we have to use DP to do the optimization. Because there is T = O(nlgn) in the middle of the T = O(n^2) and T = O(n), we can think about maybe we can optimize the algorithm to T = O(nlgn), which gives us the hint we may need sort the array.
• If the number of elements is odd, the median should be sorted_arr[len(arr) / 2]
• If the number of elements is even, the median should be the average_value_(_sorted_arr[len(arr) / 2 - 1], sorted_arr[len(arr) / 2])

Note:

• Time complexity = O(nlgn), n is the number of the given numbers. Assume we use quick sort or merge sort to sort the nums, which time complexity = O(ngln).
• Base on the requirement of this problem, we cannot use the real median of the array when the number of elements is even, we compared the results.

Time Limited Exceeded

import sys

class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        min_moves = sys.maxint
        for target_num in nums:
            move_accumulator = 0
            for num in nums:
                move_accumulator += abs(num - target_num)
                if move_accumulator >= min_moves:
                    break
            min_moves = min(min_moves, move_accumulator)

        return min_moves

Note:

• Time complexity = O(n^2), n is the number of the given numbers.