IBM面试题：n个无序整数，求第K大或者前K大的数（不要求排序输出，找到就行）
n个无序整数，求第K大或者前K大的数（不要求排序输出，找到就行），时间复杂度为O（n），各位有什么好的想法吗？
进一步如果要求排序输出的话，最好的时间复杂性是多少？
[解决办法]
就是"线性时间选择"算法,该算法如下:
STEP1. if (n<75) 排序后取第 k 个数; // 该步耗时 O(1)
STEP2. 将输入的序列分成 g=n/5 个组,将每组的中位数存入数组 B; // 该步耗时 O(n)
STEP3. 递归地,求 B 的中位数 X; // 该步耗时 T(n/5)
STEP4. 把输入序列中小于 X 的放入集合C,大于等于 X 的放入集合 D;
STEP5. if (k<=
[解决办法]
C
[解决办法]
) 递归地在 C 中找第 k 个元;
else 递归地在 D 中找第 k-
[解决办法]
C
[解决办法]
小元; // 该步耗时 T(0.75n)
总时间耗费 T(n)=T(0.2n)+T(0.75n)+O(n)=O(n)
[解决办法]
如果先排序再输出,时间耗费 T(n)=O(nlogn)
[解决办法]
给楼主个代码参考下吧，借鉴下快排的思想，就很容易明白了。
template<typename T>
int partition(T array[], int low, int high)
{
T x = array[low];
while(low < high)
{
while(low < high && array[high] <= x) --high;
array[low] = array[high];
while(low < high && array[low] >= x) ++low;
array[high] = array[low];
}
array[low] = x;
return low;
}
/*返回a中第k大的元素，复杂度为O(n)*/
void search(int *a, int i, int j, int k)
{
if(i <= j)
{
int q = partition(a, i, j);
/*if a[q] is the key looking for, then print it*/
if(q-i+1 == k)
{
/*be careful about the index*/
cout<<"The "<<q+1<<"th min number is: "<<a[q]<<endl;
return;
}
else if(q-i+1 < k)
{
/*look for the k-(q-i+1) th max number in [q+1, j]*/
search(a, q+1, j, k-(q-i+1));
}
else
{
/*look for the k th max number in [i, q-1]*/
search(a, i, q-1, k);
}
}
}
def find(a,k):
result = sorted(a[0:k])
for x in a[k:]:
if x>result[0]:
result.pop(0)
#bi sect search
lo = 0
hi = k-1
while lo<hi:
mid = (lo+hi)//2
if x>result[mid]:
lo = mid+1
else:
hi = mid
result.insert(lo, x)
print(result)
find([3,4,5,2,1,3,4,5,6],3)
Array.prototype.getElementMax = function(k) {
var i = 0, arr = this, M = Math.max.apply(Math, arr);
arr.join(",").replace(/[^,]+/g, function($){if($ == M){arr[i] = 0; return} i++});
return k ? [M].concat(arr.getElementMax(--k)) : [];
}
var arr = [], obj = {};
while (arr.length < 1000) {
var num = Math.random() * 10000 >> 0;
obj[num]
[解决办法]
(arr.push(num), obj[num] = true);
}
alert(arr.getElementMax(3).pop()); //第3（k）大整数
//alert(arr.getElementMax(3)); //前3（k）大整数
