6 language-agnostic arrays algorithm big-o selection
所以我给了一个N个不同整数的(未排序)数组A,我试图实现一个分而治之的算法来找到数组中的第K个最小元素(K≤N)(即如果它是整体最小的K = 1).该算法返回数组中第K个最小元素的值.我需要它在平均情况下在O(N)时间内运行.谁能给我一些提示？
cor*_*iKa 14
Sephy,我要非常仔细地走过去.在帮助人们使用算法时,你总是要小心,因为,我不能强调这一点,解决算法问题对于程序员来说,对于职业运动员来说什么是举重.知道如何将自己置于像计算机这样的思维模式中,您将在几年内获得报酬.因此,如果解决方案只是给你的话,那么你将成为每6个月从一个工作岗位转变为工作岗位的人,而不是那个成为首席开发人员的人,或者是一个成功的公司自己出去的人.
现在那个咆哮已经不在了......
传统上,我们认为算法循环遍历数组一次,并根据第一个结果以不同方式循环,并重复直到我们遇到某些条件,为O(n ^ 2).符合此条件的内容包括选择排序,插入排序和冒泡排序.
但它不一定是.如果我们可以正确地将数组划分为段并证明这些段的大小,我们可以将它保持在低位.
而且,对于大多数分而治之的算法,我们可以从中间开始.
Let A be an array of size N with N distinct elements in it.
Let M be the element that resides at A[N/2]
Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.
我们对A-small和A large有什么了解？它们的大小相同吗？也许,但可能不是.
是size(A-small) > k吗？或者是< k吗？
如果size(A-small) == k - 1,那不会使M成为第k个最小元素吗？
我们可以做些什么来为k创建一个新值并在这里做一些复发吗？
我不打算为你完成这个,因为应该有足够的东西来咀嚼.这些是您需要问自己的问题.@templatetypedef在正确的轨道上是100%,这只是扩展它.
如果你还有其他问题,请问他们,但是这里应该有足够的让你解决它而不会让你的精神锻炼失去理智.
作为提示,请考虑快速排序分区步骤的工作原理.它将输入分开,使枢轴位于最终位置,最小元素位于左侧,较大元素位于右侧.有了这些信息,并且知道你想要找到什么索引,你能想到一种递归找到第k个元素的方法吗？