Let S be a set of n integers stored in an array (not necessarily sorted). Design an algorithm to find the 10 largest integers in S (by creating a separate array of length 10 storing those integers). Your algorithm must finish in O(n) time.
假设S是存储在数组中的n个整数(不一定是排序的)。设计一个算法来查找S中最大的10个整数(通过创建一个长度为10的独立数组来存储这些整数)。你的算法必须在O(n)时间内完成。
I thought I could maybe answer this by using count sort and then adding last 10 elements into the new array. But apparently this is wrong. Does anyone know a better way?
我想我可以用count sort来回答这个问题然后在新的数组中加入最后10个元素。但显然这是错误的。有人知道更好的方法吗?
4 个解决方案
#1
4
Method 1: you can use FindMax() algorithm that find the max number in O(N)
and if you use it 10 time :
方法1:可以使用FindMax()算法找到O(N)中的最大值,如果使用10次:
10 * O(N) =O(N)
each time you find max num you put it in the new array and you will ignore it the next time you use FindMax();
每次找到max num时都把它放到新数组中下次使用FindMax()时就会忽略它;
Method 2:
方法2:
you can use Bubble 10 times:
你可以使用10次Bubble:
1) Modify Bubble Sort to run the outer loop at most 10 times.
2) Save the last 10 elements of the array obtained in step 1 to the new array.
10 * O(N) =O(N)
Method 3:
方法3:
You can use MAX Heap
:
可以使用MAX Heap:
1) Build a Max Heap in O(n)
2) Use Extract Max 10 times to get 10 maximum elements from the Max Heap 10
* O(logn)
O(N) + 10 * O(logN) = O(N)
#2
1
Use order statistic algorithm to find the 10th biggest element. Next, iterate over the array to find all elements which are lesser/equal it.
利用序统计算法求出第10大元素。接下来,遍历数组以查找所有元素,这些元素都小于或等于它。
TimeComplexity: O(n) for order statistic + O(n) for iterating the array once => O(n)
时间复杂度:O(n)用于迭代数组的顺序统计量+ O(n) => O(n)
#3
0
Visit :
访问:
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
They have mentioned six methods for this.
他们已经提到了六种方法。
#4
-1
Insert them in a balanced binary tree. O(N) + O(lg2 N).
将它们插入到平衡的二叉树中。O(N)+ O(lg2 N)。
#1
4
Method 1: you can use FindMax() algorithm that find the max number in O(N)
and if you use it 10 time :
方法1:可以使用FindMax()算法找到O(N)中的最大值,如果使用10次:
10 * O(N) =O(N)
each time you find max num you put it in the new array and you will ignore it the next time you use FindMax();
每次找到max num时都把它放到新数组中下次使用FindMax()时就会忽略它;
Method 2:
方法2:
you can use Bubble 10 times:
你可以使用10次Bubble:
1) Modify Bubble Sort to run the outer loop at most 10 times.
2) Save the last 10 elements of the array obtained in step 1 to the new array.
10 * O(N) =O(N)
Method 3:
方法3:
You can use MAX Heap
:
可以使用MAX Heap:
1) Build a Max Heap in O(n)
2) Use Extract Max 10 times to get 10 maximum elements from the Max Heap 10
* O(logn)
O(N) + 10 * O(logN) = O(N)
#2
1
Use order statistic algorithm to find the 10th biggest element. Next, iterate over the array to find all elements which are lesser/equal it.
利用序统计算法求出第10大元素。接下来,遍历数组以查找所有元素,这些元素都小于或等于它。
TimeComplexity: O(n) for order statistic + O(n) for iterating the array once => O(n)
时间复杂度:O(n)用于迭代数组的顺序统计量+ O(n) => O(n)
#3
0
Visit :
访问:
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
They have mentioned six methods for this.
他们已经提到了六种方法。
#4
-1
Insert them in a balanced binary tree. O(N) + O(lg2 N).
将它们插入到平衡的二叉树中。O(N)+ O(lg2 N)。