在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..等的确切计数。

Array sum =(1's count*1) + (2's count * 2) ... (9's count * 9).

总复杂度=O(logN)。

编辑:

数组中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)

Answer 2

根据推荐的答案，如何知道数组中每个元素的计数?我的理解是，二分查找会给你那个元素的第一次出现，但你仍然需要知道比它大或小的元素来计算出现次数，这样你仍然要遍历整个数组，结果是0 (N)如果我说错了请指正。