在 O(log n) 时间复杂度中查找排序数组的总和
Finding sum of a sorted array in O(log n) Time Complexity
有一个排序数组 A[1,..,n]，其中数组中的每个元素都在 [0-9] 之间，数字可以重复，条件是 A[i] <= A[i+ 1](小于等于)
有没有办法在 O(log n) 时间复杂度内计算这个？
使用二进制搜索查找第一次出现的 0，然后是第一次出现的 1，依此类推，一直到 9。这样，您就会知道 0's, 1's, 2's.. 等的确切计数在数组中。
数组总和=(1's count*1) + (2's count * 2) ... (9's count * 9).
总复杂度 = O(logN) 运行 二分查找 9 次。
有一个排序数组 A[1,..,n]，其中数组中的每个元素都在 [0-9] 之间，数字可以重复，条件是 A[i] <= A[i+ 1](小于等于)
有没有办法在 O(log n) 时间复杂度内计算这个？
使用二进制搜索查找第一次出现的 0，然后是第一次出现的 1，依此类推，一直到 9。这样，您就会知道 0's, 1's, 2's.. 等的确切计数在数组中。
数组总和=(1's count*1) + (2's count * 2) ... (9's count * 9).
总复杂度 = O(logN) 运行 二分查找 9 次。