C++實現(xiàn)查找中位數(shù)的O(N)算法和Kmin算法

更新時間：2014年09月18日 10:44:21 投稿：shichen2014

這篇文章主要介紹了C++實現(xiàn)查找中位數(shù)的O(N)算法和Kmin算法,對于C++程序算法設計有一定的借鑒價值,需要的朋友可以參考下

本文實例講述了C++實現(xiàn)查找中位數(shù)的O(N)算法和Kmin算法，分享給大家供大家參考。具體方法如下：

利用快速排序的partition操作來完成O(N)時間內(nèi)的中位數(shù)的查找算法如下：

#include <iostream>
#include <cassert>
#include <algorithm>
#include <iterator>

using namespace std;

int array[] = {1, 2, 10, 8, 9, 7, 5};
const int size = sizeof array / sizeof *array;

int partition(int *array, int left, int right)
{
 if (array == NULL)
 return -1;

 int pos = right;
 right--;
 while (left <= right)
 {
 while (left < pos && array[left] <= array[pos])
  left++;

 while (right >= 0 && array[right] > array[pos])
  right--;

 if (left >= right)
  break;

 swap(array[left], array[right]);
 }
 swap(array[left], array[pos]);

 return left;
}

int getMidIndex(int *array, int size)
{
 if (array == NULL || size <= 0)
 return -1;

 int left = 0;
 int right = size - 1;
 int midPos = right >> 1;
 int index = -1;

 while (index != midPos)
 {
 index = partition(array, left, right);

 if (index < midPos)
 {
  left = index + 1;
 }
 else if (index > midPos)
 {
  right = index - 1;
 } 
 else
 {
  break;
 }
 }

 assert(index == midPos);
 return array[index];
}

void main()
{
 int value = getMidIndex(array, size);

 cout << "value: " << value << endl;
}

尋找kmin算法如下：

int findKMin(int *array, int size, int k)
{
 if (array == NULL || size <= 0)
 return -1;

 int left = 0;
 int right = size - 1;
 int index = -1;

 while (index != k)
 {
 index = partition(array, left, right);

 if (index < k)
 {
  left = index + 1;
 }
 else if (index > k)
 {
  right = index - 1;
 } 
 else
 {
  break;
 }
 }

 assert(index == k);
 return array[index];
}

希望本文所述對大家C++程序算法設計的學習有所幫助。

您可能感興趣的文章:

C++
算法

C++使用htslib庫讀入和寫出bam文件的實例
下面小編就為大家分享一篇C++使用htslib庫讀入和寫出bam文件的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2017-11-11
C語言結(jié)構(gòu)體（Struct）詳解及示例代碼
本文主要介紹C語言結(jié)構(gòu)體的知識，學習C語言肯定需要學習結(jié)構(gòu)體，這里詳細說明了結(jié)構(gòu)體并附示例代碼，供大家參考學習，有需要的小伙伴可以參考下
2016-08-08
怎么實現(xiàn)類的成員函數(shù)作為回調(diào)函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可
2013-10-10
基于C++11實現(xiàn)手寫線程池的示例代碼
在實際的項目中,使用線程池是非常廣泛的,本文主要介紹了基于C++11實現(xiàn)手寫線程池的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
2024-08-08
C/C++ 中堆和棧及靜態(tài)數(shù)據(jù)區(qū)詳解
這篇文章主要介紹了C/C++ 中堆和棧及靜態(tài)數(shù)據(jù)區(qū)詳解的相關資料,需要的朋友可以參考下
2017-04-04
C++17使用折疊表達式實現(xiàn)一個IsAllTrue函數(shù)的過程
本文介紹了利用C++17特性實現(xiàn)IsAllTrue函數(shù)的方法,詳細講解了從基于初始化列表的初級版本到使用折疊表達式和類型萃取的高級優(yōu)化版本,需要的朋友參考下吧
2024-09-09
C語言按關鍵字搜索文件夾中文件的方法
這篇文章主要介紹了C語言按關鍵字搜索文件夾中文件的方法,涉及C語言文件操作及字符串查找的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下
2015-07-07
C語言中pthread_exit和pehread_join的使用
pthread_exit用于強制退出一個線程,pthread_join用于阻塞等待線程退出,獲取線程退出狀態(tài),本文主要介紹了C語言中pthread_exit和pehread_join函數(shù)的使用,具有一定的參考價值,感興趣的可以了解一下
2024-02-02
C++定義和初始化string對象實例詳解
這篇文章主要為大家介紹了C++定義和初始化string對象實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-12-12
C語言深入詳解四大內(nèi)存函數(shù)的使用
這篇文章主要介紹了C語言的四大內(nèi)存函數(shù)，講解了mencpy、memmove、memcmp、memset函數(shù)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步
2022-07-07