当前位置: 编程技术>c/c++/嵌入式
深入线性时间复杂度求数组中第K大数的方法详解
来源: 互联网 发布时间:2014-10-14
本文导语: 求数组中第K大的数可以基于快排序思想,步骤如下:1、随机选择一个支点2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)3、设左部分的长度为L,当K < L时,递归地在左部分找...
求数组中第K大的数可以基于快排序思想,步骤如下:
1、随机选择一个支点
2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)
3、设左部分的长度为L,
当K < L时,递归地在左部分找第K大的数
当K > L时,递归地在有部分中找第(K - L)大的数
当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数
以上思想的代码实现如下:
/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基于快速排序思想,求数组a中第k大的数,low和high分别为数组的起始和结束位置
//时间复杂度为o(n),n为数组的长度
//1
1、随机选择一个支点
2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)
3、设左部分的长度为L,
当K < L时,递归地在左部分找第K大的数
当K > L时,递归地在有部分中找第(K - L)大的数
当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数
以上思想的代码实现如下:
代码如下:
/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基于快速排序思想,求数组a中第k大的数,low和high分别为数组的起始和结束位置
//时间复杂度为o(n),n为数组的长度
//1