Algorithm学习笔记 --- 寻找 K 大数
|
Q： 给你一个无序的序列，要你找出第K大的数是什么？ Answer： Answer 1： 利用Hash，桶排序等方式，是第一个想到的（编程珠玑中所记） 假设数列中最大数为max，最小数为min，那么首先做一个数组长度为max – min + 1， 然后做散列函数为an – min，对于冲突的处理是计数，最后从后往前扫描一次整个新建的数组， 即可得到第k大的数。这样看似可以在O(n)的复杂度内解决问题，是一个经典的空间换时间的办法， 但是具体情况是，其实这个算法的时间复杂度是 O( n * ( max – min ) )的，所以这个的时间复杂度 完全取决于数组的最大与最小数的差。但是一般在实际的数据中，数列是很分散的，如果特别分散的话， 完全有可能max – min 是远大于n的，那么这个效果就非常差了， 代码如下：O( n * ( max – min ) ) //Find K-th Number
#include <iostream>
#include <stdio.h>
using namespace std;
int find_k(int p[],int n,int k)
{
int KList[k];
for(int i = 0; i < k; i++)
kList[i] = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < k; j++)
{
if(p[i] > kList[j])
{
for(int I = K - 1; I > j; I--)
{
kList[I] = kList[I - 1]
kList[j] = p[i]
break;
}
}
}
}
return kList[k - 1]
}
int main()
{
//....
//return 0
}
Answer2: ? ? 编程之美的解法：使用部分快排的方法 方法是从最开始的原始方法开始讨论展开的。得到k个最大数，首先做排序，然后取前k个即可， 而用快排或者堆排序，这样的时间复杂度是o(N*logN)，于是基于这样的时间复杂度为起点，开始逐步的优化。 优化的原因是，要得到k个最大数，只需要前k个数有序，时间复杂度的优化，只能从去除对k个以后的数进行排序展开。 优化方法如下：首先随机在数列中找到一个数，作为轴值，将数列划分成Sa和Sb两个部分，其中Sa中存放大于或等于轴值的数，Sb存放小于轴值 的数，划分完成后，有如下两种情况：
代码如下：o(N*logN) int find_k(vector find,int k)
{
if(find.size() < k)
{
return 0;
}
int p = find.at(0);
vector findA,findB;
for(int i = 1; i < find.size(); i++)
{
if(find.at(i) >= p)
findA.push_back(find.at(i))
else
findB.push_back(find.at(i))
}
if(findA.size() == (k - 1))
{
return p;
}
else if(findA.size(0 > (k - 1))
{
return find_k(findA,k);
}
else
{
return find_k(findB,k findA.size());
}
}
Answer3:用 小顶堆优化 其实这是没有意义的事情，毕竟我要的只是第k个数，所以我只要知道我那k个数组中， 最小的那个数即可，也就是一直保存的k个数，可以是无序的，但是，一定要知道其中最小值， 有一个最小值，并且整体不一定有序，这样的数据结构一下就想到了最小值堆，首先将堆的接口声明如下 代码如下： O(N * logK) classminHeap{
private:
int*Heap;//用于存放堆元素的数组
intsize;//数组大小
intn;//堆中元素个数
voidshiftdown(int);//堆的下拉操作
public:
minHeap(int*Heap,intnum,intmax)
boolisLeaf(intpos)const
intleftchild(intpos)const
intrightchild(intpos)const
intparent(intpos)const
boolinsert(constint);
boolremoveMin(int&);
intgetMin();
};
（编辑：温州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
