JobHunting版 - The time complexity on finding the kth largest element in a |
|---|
|
| 相关主题 |
|---|
| ● partition array problem | ● find elements in an array that sum up to a given number | | ● array a1,a2,... ,an, b1,b2,..., bn | ● Find the intersection of two sorted arrays【扩展】 | | ● 请问G一题 | ● Given an array of N integers from range ［0, N] and one is missing. Find the missing number. | | ● MS a0, a1, ..., b0, b1... 问题 | ● finding the majority element in an array? | | ● 问道算法题 | ● 关于quicksort的两种实现方法 | | ● find Kth Largest Element 有没有更简化的解法 | ● Find the Kth smallest element in 2 sorted | | ● 求教一个onsite面试题目 | ● 果家OA, 关于数组中S[K]的最大长度,要求O(N)时间与空间 | | ● 一个算法题：Selecting median of three sorted arrays | ● 请教一道题目 |
|
|
|
|
|
r****o
发帖数: 1950 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: The time complexity on finding the kth largest element in a
发信站: BBS 未名空间站 (Tue Jun 1 22:42:09 2010, 美东)
We can use the partition() in qsort. Each time, we can partition the array
into two parts, array_a and array_b. Let the number of elements in array_a
and array_b be sa and sb, respectively.
If sa is smaller than k, then find the (k-sa)th largest element in array_b;
If sa is larger than or equal to k, then find | g*****a
发帖数: 1457 | 2 the worst case is that every round of recursion, sb is 1.
the O(n) = n + ( n-1) + (n-2)... + k = O(n^2) | g*****a
发帖数: 1457 | 3 why not just use max heap or loser tree |
|
|
|
|
| 相关主题 |
|---|
| ● 请教一道题目 | ● 问道算法题 | | ● 向各位大侠请教几道面试题的思路 | ● find Kth Largest Element 有没有更简化的解法 | | ● Quick sort为什么需要logN的memory? | ● 求教一个onsite面试题目 | | ● Find the first k smallest numbers in an array. | ● 一个算法题：Selecting median of three sorted arrays | | ● partition array problem | ● find elements in an array that sum up to a given number | | ● array a1,a2,... ,an, b1,b2,..., bn | ● Find the intersection of two sorted arrays【扩展】 | | ● 请问G一题 | ● Given an array of N integers from range ［0, N] and one is missing. Find the missing number. | | ● MS a0, a1, ..., b0, b1... 问题 | ● finding the majority element in an array? |
|
|
|
