LeetCode: 2256-Minimum Average Difference 解題紀錄

Last Updated on 2022-12-05 by Clay

題目

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，然後把右半部分設定為全部加總的值。接著遍歷整個陣列，每次都把左半部分的值加上 nums[i]、然後右半部分減去 nums[i]。當然，也要每次都計算著兩個部分分別有多少數值才能求平均。

有一個需要小心的地方是，由於加總後的數值很大，所以至少需要使用 long 來儲存。

複雜度

Time Complexity	O(n)
Space Complexity	O(1)

C++ 範例程式碼

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        // Init
        int index = 0;
        int minDiff = INT_MAX;
        long left = 0;
        long right = (long)accumulate(nums.begin(), nums.end(), 0L);
        int leftNum = 0;
        int rightNum = nums.size();
        
        // Loop
        for (int i=0; i<nums.size(); ++i) {
            left += nums[i];
            right -= nums[i];
            
            // Calculate the difference between the average of the left and right part
            ++leftNum;
            rightNum = max(1, rightNum-1);
            int avgDiff = abs((int)(left/leftNum) - (int)(right/rightNum));
            
            // Update the minimum average difference
            if (minDiff > avgDiff) {
                minDiff = avgDiff;
                index = i;
            }
        }
                                   
        return index;
    }
};

Python 範例程式碼

class Solution:
    def minimumAverageDifference(self, nums: List[int]) -> int:
        # Init
        index = 0
        min_diff = 2147483647
        left = 0
        right = sum(nums)
        left_num = 0
        right_num = len(nums)
        
        # Loop
        for i in range(len(nums)):
            left += nums[i]
            right -= nums[i]
            
            # Calculate the difference between the average of the left and right part
            left_num += 1
            right_num = max(1, right_num-1)
            
            diff = abs(left//left_num - right//right_num)
            if min_diff > diff:
                index = i
                min_diff = diff
                                   
        return index

---

References

• 2256. Minimum Average Difference

---

Read More

• LeetCode 解題紀錄目錄