内容简介:本文是对:octopus:本文的翻译原文和代码可以查看:octopus:
本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club 是raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+:star:️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
:octopus: andyRon/swift-algorithm-club-cn 是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习 。当然也欢迎加:star:️, 。
本文的翻译原文和代码可以查看:octopus: swift-algorithm-club-cn/Count Occurrences
目标:计算某个值在数组中出现的次数。
显而易见的方法是从数组的开头直到结束的 线性搜索 ,计算您遇到该值的次数。 这是一个 O(n) 算法。
但是,如果数组已经排过序的,则可以通过使用修改 二分搜索 来更快的完成这个任务,时间复杂度为 O(logn) 。
假设我们有以下数组:
[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] 复制代码
如果我们想知道值 3
出现的次数,我们可以进行常规二分搜索。 这可以获得四个 3
索引中的一个:
[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] * * * * 复制代码
但是,这仍然没有告诉你有多少其它的 3
。 要找到那些其它的 3
,你仍然需要在左边进行线性搜索,在右边进行线性搜索。 在大多数情况下,这将是足够快的,但在最坏的情况下 —— 当这个数组中除了之前的一个 3
之外就没有其它 3
了 —— 这样时间复杂度依然是 O(n)
。
一个诀窍是使用两个二分搜索,一个用于查找 3
开始(左边界)的位置,另一个用于查找 3
结束的位置(右边界)。
代码如下:
func countOccurrencesOfKey(_ key: Int, inArray a: [Int]) -> Int { func leftBoundary() -> Int { var low = 0 var high = a.count while low < high { let midIndex = low + (high - low)/2 if a[midIndex] < key { low = midIndex + 1 } else { high = midIndex } } return low } func rightBoundary() -> Int { var low = 0 var high = a.count while low < high { let midIndex = low + (high - low)/2 if a[midIndex] > key { high = midIndex } else { low = midIndex + 1 } } return low } return rightBoundary() - leftBoundary() } 复制代码
请注意,辅助函数 leftBoundary()
和 rightBoundary()
与 二分搜索
算法非常相似。最大的区别在于,当它们找到 搜索键
时,它们不会停止,而是继续前进。
要测试此算法,将代码复制到 playground,然后执行以下操作:
let a = [ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] countOccurrencesOfKey(3, inArray: a) // returns 4 复制代码
请记住:使用的数组,确保已经 排序 过!
来看看这个例子的过程。 该数组是:
[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] 复制代码
为了找到左边界,我们从 low = 0
和 high = 12
开始。 第一个中间索引是 6
:
[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] * 复制代码
通过常规二分搜索,你现在就可以完成了,但是我们不只是查看是否出现了值 3
—— 而是想要找到它 第一次
出现的位置。
由于该算法遵循与二分搜索相同的原理,我们现在忽略数组的右半部分并计算新的中间索引:
[ 0, 1, 1, 3, 3, 3 | x, x, x, x, x, x ] * 复制代码
我们再次找到了一个 3
,这是第一个。 但算法不知道,所以我们再次拆分数组:
[ 0, 1, 1 | x, x, x | x, x, x, x, x, x ] * 复制代码
还没完, 再次拆分,但这次使用右半部分:
[ x, x | 1 | x, x, x | x, x, x, x, x, x ] * 复制代码
数组不能再被拆分,这意味着左边界在索引3处。
现在让我们重新开始,尝试找到右边界。 这非常相似,所以我将向您展示不同的步骤:
[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ] * [ x, x, x, x, x, x, x | 6, 8, 10, 11, 11 ] * [ x, x, x, x, x, x, x | 6, 8, | x, x, x ] * [ x, x, x, x, x, x, x | 6 | x | x, x, x ] * 复制代码
右边界位于索引7处。两个边界之间的差异是7 - 3 = 4,因此数字 3
在此数组中出现四次。
每个二分搜索需要4个步骤,所以总共这个算法需要8个步骤。 在仅有12个项的数组上获得的收益不是很大,但是数组越大,该算法的效率就越高。 对于具有1,000,000个项目的排序数组,只需要2 x 20 = 40个步骤来计算任何特定值的出现次数。
顺便说一句,如果你要查找的值不在数组中,那么 rightBoundary()
和 leftBoundary()
返回相同的值,因此它们之间的差值为0。
这是一个如何修改基本二分搜索以解决其它算法问题的示例。 当然,它需要先对数组进行排序。
作者:Matthijs Hollemans
翻译: Andy Ron
校对: Andy Ron
以上所述就是小编给大家介绍的《【译】Swift算法俱乐部-统计出现次数》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例
- Fundebug 微信小程 BUG 监控插件更新至 1.2.1,优化错误上报次数的限制算法,新增 silentHttpHead...
- Django annotation,减少IO次数利器
- 找出数组中出现次数超过一半的数
- 使用golang反向代理统计api访问次数
- Glow使用小结 - 统计Key出现的次数
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
算法竞赛入门经典
刘汝佳 / 清华大学出版社 / 2009-11 / 24.00元
《算法竞赛入门经典》是一本算法竞赛的入门教材,把C/C++语言、算法和解题有机地结合在了一起,淡化理论,注重学习方法和实践技巧。全书内容分为11章,包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法,覆盖了算法竞赛入门所需的主要知识点,并附有大量习题。书中的代码规范、简洁、易懂,不仅能帮助......一起来看看 《算法竞赛入门经典》 这本书的介绍吧!