leetcode: 462. Minimum Moves to Equal Array Elements II

kldaji·2022년 7월 1일
0

leetcode

목록 보기
37/42

problem

use average

  • incorrect answer
class Solution {
    fun minMoves2(nums: IntArray): Int {
        val average = nums.sum() / nums.size
        var answer = 0
        nums.forEach { num ->
            answer += Math.abs(average - num)
        }
        return answer
    }
}

use median

class Solution {
    fun minMoves2(nums: IntArray): Int {
        nums.sort()
        val size = nums.size
        val mid = if (size.and(1) == 1) nums[size / 2] else (nums[size / 2] + nums[size / 2 - 1]) / 2
        
        var answer = 0
        nums.forEach { num ->
            answer += Math.abs(num - mid)
        }
        return answer
    }
}

reduce the problem n -> n-2 -> n-4 -> ...

  • we don't need specific meeting point, just calculate (max - min) of array.
  • let's consider max is 9, and min is 1.
  • if we pick the meeting point is 1, the amount of move count will be 8.
  • if we pick 2, it will be also 8, and so on.
  • so, we just consider max and min value in array then, reduce the array size using two pointers.
  • if so, why these approach is same to get the median value?
  • let's assume that we pick the meeting point to median value.
  • now we can get the amount of move count to (max - median) + (min - median).
  • if the size of array is odd, median value does not need to move anymore.
  • therefore, pick the meeting value to median value can be the answer of this problem.
class Solution {
    fun minMoves2(nums: IntArray): Int {
        nums.sort()
        var left = 0
        var right = nums.size - 1
        var answer = 0
        while (left < right) {
            answer += (nums[right] - nums[left])
            left++
            right--
        }
        return answer
    }
}
profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.

0개의 댓글