快捷導(dǎo)航

深入線性時(shí)間復(fù)雜度求數(shù)組中第K大數(shù)的方法詳解

更新時(shí)間：2013年05月24日 12:10:33 作者：

本篇文章是對(duì)線性時(shí)間復(fù)雜度求數(shù)組中第K大數(shù)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

求數(shù)組中第K大的數(shù)可以基于快排序思想，步驟如下：
1、隨機(jī)選擇一個(gè)支點(diǎn)
2、將比支點(diǎn)大的數(shù)，放到數(shù)組左邊；將比支點(diǎn)小的數(shù)放到數(shù)組右邊；將支點(diǎn)放到中間(屬于左部分)
3、設(shè)左部分的長(zhǎng)度為L(zhǎng)，
當(dāng)K < L時(shí)，遞歸地在左部分找第K大的數(shù)
當(dāng)K > L時(shí)，遞歸地在有部分中找第(K - L)大的數(shù)
當(dāng)K = L時(shí)，返回左右兩部分的分割點(diǎn)（即原來的支點(diǎn)），就是要求的第K大的數(shù)
以上思想的代碼實(shí)現(xiàn)如下：

復(fù)制代碼代碼如下:

/**
線性時(shí)間復(fù)雜度求數(shù)組中第K大數(shù)
** author :liuzhiwei 
** data   :2011-08-07  
**/
#include "iostream"
using namespace std;
//基于快速排序思想，求數(shù)組a中第k大的數(shù)，low和high分別為數(shù)組的起始和結(jié)束位置
//時(shí)間復(fù)雜度為o(n)，n為數(shù)組的長(zhǎng)度
//1<=k<=n
//如果存在，返回第k大數(shù)的下標(biāo)，否則返回-1
int selectk(int a[], int low, int high, int k)
{
 if(k <= 0)
  return -1;
 if(k > high - low + 1)
  return -1;
 int pivot = low + rand()%(high - low + 1);    //隨即選擇一個(gè)支點(diǎn)
 swap(a[low], a[pivot]);
 int m = low;
 int count = 1;
 //一趟遍歷，把較大的數(shù)放到數(shù)組的左邊
 for(int i = low + 1; i <= high; ++i)
 {
  if(a[i] > a[low]) 
  {
   swap(a[++m], a[i]);
   count++;              //比支點(diǎn)大的數(shù)的個(gè)數(shù)為count-1
  }
 }
 swap(a[m], a[low]);           //將支點(diǎn)放在左、右兩部分的分界處
 if(count > k)
 {
  return selectk(a, low, m - 1, k);
 }
 else if( count < k)
 {
  return selectk(a, m + 1, high, k - count);
 }
 else
 {
  return m;
 }
}
int main(void)
{
 int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
 int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 5);
 cout<<(r == -1 ? r : a[r])<<endl;
 system("pause");
 return 0;
}

稍微改動(dòng)一下，就可以修改為求數(shù)組中第K小數(shù)
完整的代碼如下：

復(fù)制代碼代碼如下:

/**
線性時(shí)間復(fù)雜度求數(shù)組中第K小數(shù)
** author :liuzhiwei 
** data   :2011-08-07  
**/
#include "iostream"
using namespace std;
//基于快速排序思想，求數(shù)組a中第k小的數(shù)，low和high分別為數(shù)組的起始和結(jié)束位置
//時(shí)間復(fù)雜度為o(n)，n為數(shù)組的長(zhǎng)度
//1<=k<=n
//如果存在，返回第k小數(shù)的下標(biāo)，否則返回-1
int selectk(int a[], int low, int high, int k)
{
 if(k <= 0)
  return -1;
 if(k > high - low + 1)
  return -1;
 int pivot = low + rand()%(high - low + 1);    //隨即選擇一個(gè)支點(diǎn)
 swap(a[low], a[pivot]);
 int m = low;
 int count = 1;
 //一趟遍歷，把較小的數(shù)放到數(shù)組的左邊
 for(int i = low + 1; i <= high; ++i)
 {
  if(a[i]<a[low]) 
  {
   swap(a[++m], a[i]);
   count++;              //比支點(diǎn)小的數(shù)的個(gè)數(shù)為count-1
  }
 }
 swap(a[m], a[low]);           //將支點(diǎn)放在左、右兩部分的分界處
 if(k < count)
 {
  return selectk(a, low, m - 1, k);
 }
 else if( k > count)
 {
  return selectk(a, m + 1, high, k - count);
 }
 else
 {
  return m;
 }
}
int main(void)
{
 int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
 int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 23);
 cout<<(r == -1 ? r : a[r])<<endl;
 system("pause");
 return 0;
}