问用O(log )时间复杂度求排序数组的和
EN

Stack Overflow用户

提问于 2022-05-15 16:58:36

回答 1查看 457关注 0票数 4

有一个排序的数组A1，..，n，其中数组中的每个元素都在0-9之间，数字可以在Ai <= Ai+1 (小于等于)的条件下重复。

有没有办法在O(log )时间复杂度中计算这一点？

回答已采纳

发布于 2022-05-15 17:01:29

使用二进制搜索查找第一次出现的0，然后找到第一次出现的1，等等，直到9。这样，您就可以知道数组中0's, 1's, 2's..等的确切数量。

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

运行9次二进制搜索的总复杂度= O(logN)。

票数 8

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/72250382

复制

相似问题

问用O(log )时间复杂度求排序数组的和EN