1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int minimumAverageDifference(int[] nums) {
long firstPartSum = 0, secondPartSum = 0;
for (int num : nums) {
secondPartSum += num;
}
long minDiff = Integer.MAX_VALUE, minIndex = -1;
for (int i = 0; i < nums.length; i++) {
firstPartSum += nums[i];
secondPartSum -= nums[i];
long currDiff = i == nums.length - 1 ? firstPartSum / nums.length
: Math.abs(firstPartSum / (i + 1) - secondPartSum / (nums.length - i - 1));
if (currDiff < minDiff) {
minDiff = currDiff;
minIndex = i;
}
}
return (int) minIndex;
}
}
|
prefix sum就可以了. 一个变量存前一部分的sum, 一个变量存后一部分的sum. 需要注意的是到最后一个位置的时候不要除以0. 这也是currDiff为什么需要一个if判断.
时间复杂度: O(n)
空间复杂度: O(1)
