2256. Minimum Average Difference
Description
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 then
elements divided (integer division) byn
. - The average of
0
elements is considered to be0
.
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
Solutions
Solution 1: Traverse
We directly traverse the array $nums$. For each index $i$, we maintain the sum of the first $i+1$ elements $pre$ and the sum of the last $n-i-1$ elements $suf$. We calculate the absolute difference of the average of the first $i+1$ elements and the average of the last $n-i-1$ elements, denoted as $t$. If $t$ is less than the current minimum value $mi$, we update the answer $ans=i$ and the minimum value $mi=t$.
After the traversal, we return the answer.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|