如何在不对数组进行排序的情况下在未排序的数组中找到第k个最小整数? [英] How to find kth smallest integer in an unsorted array without sorting the array?
问题描述
因此，我得到了一个由N个不同整数组成的(未排序)数组A，我试图实现分治算法，以找到数组中第K个最小元素(K≤N)(即如果K = 1，则总体最小).该算法返回数组中第K个最小元素的值.在平均情况下，我需要它在O(N)时间运行.有人可以给我一些提示吗?
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小和A大了解什么?它们大小相同吗?也许可以，但是可能不会.
是size(A-small) > k吗?还是< k?
如果是size(A-small) == k - 1，那不是会使M成为第k个最小元素吗?
我们是否可以做一些事情来为k创建一个新值并在此处进行一些重复操作?
我不会为您完成此操作，因为应该有很多要咀嚼的内容.这些是您需要问自己的问题. @templatetypedef在正确的轨道上是100％，这只是在它上面扩展.
如果您还有其他问题，请询问他们，但是这里应该有足够的内容使您能够解决它，而不会影响您的脑力锻炼.
So I am given an (unsorted) array A of N distinct integers, I am trying to implement a divide-and-conquer algorithm to find the Kth smallest element (K ≤ N) in the array (i.e. it would be the overall smallest if K=1). The algorithm returns the value of the Kth smallest element in the array. I need it to run in O(N) time in the average case. Could anyone give me some hints?
Sephy, I'm going to walk this through very carefully. You always have to be careful when helping people with algorithms, because, and I cannot stress this enough, solving algorithm problems are to programmers what weight-lifting is to professional athletes. Knowing how to put yourself into the mode of thinking like a computer is what you will get paid to do in a few years. So if the solutions are just given to you, you're going to be the guy that bounces from job to job every 6 months instead of the guy who becomes the lead developer, or goes out on his own with a successful company.
Now that that rant is out of the way...
Traditionally, we think of algorithms that loop through the array once, and loop through it differently based on the first result, and repeat until we met some condition, to be O(n^2). Things that meet this criteria are selection sort, insertion sort, and bubble sort.
But it doesn't have to be. If we can properly divide the array into segments and prove the size of those segments, we can keep it on a low order.
And, with most divide and conquer algorithms, we can start in the middle.
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.
What do we know about A-small and A large? Are they the same size? Maybe, but probably not.
Is size(A-small) > k? or is it < k?
If size(A-small) == k - 1, wouldn't that make M the kth smallest element?
Is there something we can do to create a new value for k and do some recurrsion here?
I'm not going to finish this for you, because there should be plenty to chew on. These are the questions you need to ask yourself. @templatetypedef is 100% on the right track, this is just expanding on it.
If you have some more questions, ask them, but there should be enough here to allow you to solve it without robbing you of your mental exercise.
这篇关于如何在不对数组进行排序的情况下在未排序的数组中找到第k个最小整数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
