[LeetCode] 2256. Minimum Average Difference

2256. Minimum Average Difference

Medium

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

• The absolute difference of two numbers is the absolute value of their difference.
• The average of n elements is the sum of the n elements divided (integer division) by n.
• The average of 0 elements is considered to be 0.

 

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

---

문제 풀이

• 숫자 배열이 주어진다. 
• 0부터 i 까지의 숫자 합 평균(i+1로 합을 나눈다.)과 i+1 부터 끝까지의 합 평균(n - i - 1로 합을 나눈다.)의 차가 가장 작은 값을 구해야한다.
• 가장 작은 값을 가지는 위치를 리턴하면 된다. 
• 만약 다수의 정답이 있다면 인덱스는 가장 작은 값이어야하며, n개의 숫자의 합 평균은 전체 합 나누기 n이다.
• 그리고 0의 평균은 0이다.
• 제한 사항을 보면 10^5 이기 때문에 O(N)으로 풀어야한다.
• prefix sum을 활용하여 풀어야한다.
• 처음 index 1자리 부터 끝까지 숫자들을 더하여 시작한다. 
• 첫번째 정답은 미리 구하는데 인덱스 0 위치의 숫자 한개와 1부터 n(배열의 끝)까지의 합 평균으로 절대값을 계산한다.
• 이후, 인덱스 1부터 진행하여 왼쪽 파트에는 인덱스 i의 값을 빼고 평균을 구하고, 오른쪽 파트에는 인덱스 i의 값을 더해 평균을 계산한다.
• 주의할 점은 평균을 구할때 0이 들어갈 수 있기 때문에 이를 예외 처리해주어야 한다. 

소스 코드

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        total1 = nums[0]
        total2 = sum(nums[1:])
        ans = abs(total1 - total2//(n - 1))
        ans_i = 0
        for i in range(1, n):
            total1 += nums[i]
            total2 -= nums[i]
            l = total1 // (i + 1) if total1 > 0 else 0
            r = total2 // (n - i - 1) if total2 > 0 else 0
            if ans > abs(l - r):
                ans = abs(l - r)
                ans_i = i
        return ans_i