以 O(log n) 时间复杂度查找已排序数组的总和

Question

有一个排序数组 A[1,..,n]，其中数组中的每个元素都在 [0-9] 之间，并且数字可以在条件下重复，即 A[i] <= A[i+1]（小于等于）

有没有办法以 O(log n) 时间复杂度计算这个？

Answer 1

使用二分查找查找第一次出现的 0，然后查找第一次出现的 1，依此类推，直到 9。这样，您就可以知道0's, 1's, 2's..数组中 etc 的准确计数。

数组总和 = (1's count*1) + (2's count * 2) ... (9's count * 9).

总复杂度 =O(logN)运行二分查找 9 次。

编辑：

x数组中的计数将是

If `x` isn't the largest element
count(x) = (first index of the next greatest number) - (first index of x)

Else
count(x) = length of array - (first index of x)