深入線性時(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)如下:
/**
線性時(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ù)
完整的代碼如下:
/**
線性時(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;
}
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;
}
相關(guān)文章
C語言實(shí)現(xiàn)密碼強(qiáng)度檢測(cè)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)密碼強(qiáng)度檢測(cè),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-03-03C語言三分鐘精通時(shí)間復(fù)雜度與空間復(fù)雜度
算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。其作用:?時(shí)間復(fù)雜度是度量算法執(zhí)行的時(shí)間長(zhǎng)短;而空間復(fù)雜度是度量算法所需存儲(chǔ)空間的大小2022-02-02關(guān)于C++靜態(tài)數(shù)據(jù)成員的實(shí)現(xiàn)講解
今天小編就為大家分享一篇關(guān)于關(guān)于C++靜態(tài)數(shù)據(jù)成員的實(shí)現(xiàn)講解,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2018-12-12C語言數(shù)據(jù)結(jié)構(gòu)與算法時(shí)間空間復(fù)雜度基礎(chǔ)實(shí)踐
這篇文章主要為大家介紹了C語言數(shù)據(jù)結(jié)構(gòu)與算法中時(shí)間空間復(fù)雜度的基礎(chǔ)實(shí)踐,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步2022-02-02C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法詳細(xì)講解
這篇文章主要介紹了C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-11-11