深圳建西站,软件定制开发介绍,四川招标采购网,php家具网站模版参考博客#xff1a;传送门
在上面的博客中介绍了求序列第K大的几种算法#xff0c;感觉收益良多#xff0c;其中最精巧的还是利用快速排序的思想O(n)查询的算法。仔细学习以后我将其中的几个实现了一下。
解法 1#xff1a;
将乱序数组从大到小进行排序然后取出前K大传送门
在上面的博客中介绍了求序列第K大的几种算法感觉收益良多其中最精巧的还是利用快速排序的思想O(n)查询的算法。仔细学习以后我将其中的几个实现了一下。
解法 1
将乱序数组从大到小进行排序然后取出前K大总的时间复杂度为O(nlogn)
解法 2
利用选择排序或交互排序取出前K大总的时间复杂度为O(nk)
解法 3
借鉴快速排序的思想复杂度近似为O(n)
#includecstdio
#includealgorithm
#includecstdlib
using namespace std;int kth_number(int *a,int l,int r,int k)
{if(r-l 1) return a[l];int keya[l];int indexl;for(int il1;ir;i){if(a[i]key) continue;else{index;swap(a[i],a[index]);}}swap(a[index],a[l]);if(r-index k) return a[index];if(r-index-1 k) return kth_number(a,index1,r,k);else return kth_number(a,l,index,k-rindex);
}
测试程序
#includecstdio
#includeKth_number.husing namespace std;int main()
{int n,k;const int MAXN1005;int a[MAXN];printf(n); scanf(%d,n);printf(k); scanf(%d,k);if(kn) kn;printf(please input %d number:\n,n);for(int i0;in;i)scanf(%d,a[i]);printf(the %dth number of array is %d\n,k,kth_number(a,0,n,k));return 0;
}
运行结果 解法 4
借助堆排序的思想将前K个数字弹出复杂度为建立堆的O(4n)加上k次堆排序O(logn)为O(4nklogn)
实现程序
#includecstdio
#includecstdlib
#includeclimits
#includealgorithm
#includesys/types.h
#includesys/wait.h
#includefcntl.h
#includeunistd.husing namespace std;void Adjust(int *a, int n, int i)
{int x a[i];for(int k i1; k n; k k1){if(k1 n a[k] a[k1])k;if(a[k] x){a[i] a[k];i k;}else{break;}}a[i] x;
}void MakeHeap(int *a, int n)
{for(int i n/2;i 0;--i){Adjust(a, n, i);}
}void HeapSort(int *a,int n,int k,int *ans)
{int mn-k;for(int i n; i m; i--){swap(a[1], a[i]);Adjust(a, i-1, 1);}*ans a[m1];
}int main(int argc, char* argv[])
{int n;const int MAXN 1024;scanf(%d, n);int a[MAXN] {0};for(int i 1; i n; i){scanf(%d, a[i]);}int k;scanf(%d, k);if(k n) k n;MakeHeap(a, n);int ans;HeapSort(a, n, k, ans);printf(ans%d\n, ans);return 0;
}
测试结果 解法 5
维护一个大小为k的小顶堆对于数组中的每一个元素判断与堆顶的大小若堆顶较大则不管否则弹出堆顶将当前值插入到堆中。时间复杂度O(4knlogk)
实现程序
#includecstdio
#includecstringusing namespace std;void Adjust(int *a,int n,int i)
{int xa[i];for(int ki1;kn;k1){if(k1n a[k]a[k1])k;if(a[k]x){a[i]a[k];ik;}else break;}a[i]x;
}
void MakeHeap(int *a,int n)
{for(int in/2;i0;--i){Adjust(a,n,i);}
}
int KthNumber(int *a,int n,int k)
{
// int *bnew int[k];int b[1024];for(int i1;ik;i){b[i]a[i];}MakeHeap(b,k);for(int ik1;in;i){if(a[i]b[1]){b[1]a[i];Adjust(b,k,1);}}return b[1];
}int main()
{int n,k;printf(n); scanf(%d,n);printf(k); scanf(%d,k);
// int* a new int[n];int a[1024]{0};for(int i1;in;i)scanf(%d,a[i]);printf(%d\n,KthNumber(a,n,k));
// delete a;return 0;
}
测试结果 解法 6:
利用Hash保存数组中元素出现的次数利用计数排序的思想线性从大到小扫描中得到结果时间复杂度为O(n)
