C++实现查找中位数的O(N)算法和Kmin算法

本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法，分享给大家供大家参考。具体方法如下：

利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下：

#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++程序算法设计的学习有所帮助。

赞 (0)

相关推荐

  • C++二维数组中的查找算法示例

    本文实例讲述了C++二维数组中的查找算法.分享给大家供大家参考,具体如下: 一.问题: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 二.实现代码: #include <iostream> #include <vector> using namespace std; bool Find(int target, vector<vector<int>

  • 海量数据处理系列之:用C++实现Bitmap算法

    bitmap是一个十分有用的结构.所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素.由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省. 适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码扩展:bloom filter可以看做是对bit-map的扩展问题实例:1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数.8位最

  • C++实现简单遗传算法

    本文实例讲述了C++实现简单遗传算法.分享给大家供大家参考.具体实现方法如下: //遗传算法 GA #include<iostream> #include <cstdlib> #include<bitset> using namespace std; const int L=5; //定义编码的长度 int f(int x) //定义测设函数f(x) { int result; result=x*x*x-60*x*x+900*x+100; return result;

  • C++堆排序算法的实现方法

    C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++实现的O(n)复杂度内查找第K大数算法示例

    本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法.分享给大家供大家参考,具体如下: 题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积. 从题目我们知道只有两种结果存在: 1)三个最大的正整数相乘: 2)一个最大的正整数和两个最小的负数相乘. 所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果. 参考代码:http://www.jb51.net/artic

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • C++实现矩阵原地转置算法

    C++实现矩阵原地转置算法

    本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析 下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • C++二分查找(折半查找)算法实例详解

    本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复

  • C++基本算法思想之穷举法

    C++基本算法思想之穷举法

    穷举算法(Exhaustive Attack method)是最简单的一种算法,其依赖于计算机的强大计算能力来穷尽每一种可能性,从而达到求解问题的目的.穷举算法效率不高,但是适应于一些没有规律可循的场合. 穷举算法基本思想穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下: (1)对于一种可能的情况,计算其结果. (2)判断结果是否符合要求,如果不满足则执行第(1)步来搜索下一个可能的情况:如果符合要求,则表示寻找到一个正确答案. 在使用穷举法时,需要明确问题的答案的范围,这

  • C++实现迷宫算法实例解析

    本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

  • c++二叉树的几种遍历算法

    1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode)  return;    visit(pNode);   BT_PreOrder(pNode->left); BT_PreOrder(pNode->right);   }// 中序遍历void BT_PreOrder(BiTreePtr pNode){  if (!pNode)  return;     BT_PreOrder(

随机推荐