C++算法之在无序数组中选择第k小个数的实现方法

本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考，具体如下：

从一个无序的整型数组中选出第k小的数，如k=1为最小数，k=n为最大数。这里数组可以是有重复的值！

下面是自己写的一个函数，记在此处来记忆我留下的痕迹！

//选择无序数组中第k小的数
#include <iostream>
using namespace std ;
bool failed = false ;
//这里只考虑数组是int型的
int findnumber(int *array,int start , int end, int k)
{
  if(array == NULL || start > end || k < start || k > end+1 || k <= 0 )
  {
    failed = true ;
    return 0;
  }
  if(start == end)
  {
    return array[start] ;
  }
  int len = end - start + 1 ;
  int tmp = 0 ;
  int ps = rand()%len +start ;
  int tk = k ;
  while(true)
  {
   //分割两数组
   int f = start ;
   int t = array[ps] ;
   int equalnum = 0 ;
   for(int i = start ; i <= end ; i ++ )
   {
        if(array[i]< t )
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
        }else if(array[i] == t)
        {
          tmp = array[f];
          array[f] = array[i];
          array[i] = tmp ;
          f ++ ;
          equalnum ++ ;
        }
    } //end
    f--;
    if(equalnum > tk && (f - start + 1) == equalnum)
    {
      return t ;//这里是记录数据相等的数目，当我们从开始start处到最后处end都被这个值给充斥了，那么肯定是这里面的值了，再进行下去就会陷入死循环了。
    }
    if(tk == (f - start + 1) )
    {
      return t ;
    }
    if((f - start + 1 ) > tk )
    {
      end = f ;
    }else
    {
       start = f + 1  ;
       tk = k - start  ; //这个地方犯过错误，就是写成了k=k-start，在调试的时候老发现无限的循环。后来打印k的值的时候发现k的值都***为负了。这个bug，这个过错使得在一次运行可能会得到正确的数据，但是多次运行后程序就崩溃。
     }
     len = end - start + 1 ;
     ps = rand()%len +start ;
  }
}
int main()
{
  int array[10] = {1,1,1,2,2,1,4,1,1,1};
  for(int i = 0 ; i < 10 ; i ++ )
  {
    cout<<findnumber(array,0,9,i+1)<<endl;
  }
  system("pause");
  return 0 ;
}

先想好，分析好问题，自己脑中构思好了编写的思路，且想好了程序出错的地方再编程，这样会快的很多，而不是一看到问题就框框的在电脑上敲。

希望本文所述对大家C++程序设计有所帮助。

赞 (0)

相关推荐

  • 浅谈C++内存分配及变长数组的动态分配

    第一部分 C++内存分配 一.关于内存 1.内存分配方式 内存分配方式有三种: (1)从静态存储区域分配.内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在 例如全局变量,static变量. (2)在栈上创建.在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存 储单元自动被释放.栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限. (3) 从堆上分配,亦称动态内存分配.程序在运行的时候用malloc或new申请任意多少的内存,程序员

  • C++中用new创建二维数组和指针数组实例代码

    使用new 创建二维数组方法 #include <iostream> using namespace std; void main() { //用new创建一个二维数组,有两种方法,是等价的 //一: int (*p)[10] = new int[5][10]; //二: int **p = new int* [5]; for(int i=0;i <5;i++) p[i] = new int[10]; //指针数组的创建,也有两种方法 //一: char **pa = new char*

  • 浅析C/C++,Java,PHP,JavaScript,Json数组、对象赋值时最后一个元素后面是否可以带逗号

    1 C,C++,Java,PHP都能容忍末尾的逗号 C,C++,Java中对数组赋值时,最后一个元素末尾的逗号可有可无.下面两行代码对这些语言来说是等效的. int a[] = {1,2,3}; /* 正确 */ int a[] = {1,2,3,}; /* 正确 */ PHP这一点也继承了C的特点,下面的两行代码等效. $a = array(1,2,3); /* 正确 */ $a = array(1,2,3,); /* 正确 */ 2 JavaScript视末尾逗号为语法错误! 然而到了Jav

  • C++中求旋转数组中的最小数字（经典面试题）

    面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增数组的旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. 算法: (1)当输入的旋转数组非法时:处理! (2)当输入的旋转数组正常时,index1 = 0:index2=length-1: a:如果arry[index1] <arry[index2]时:说明数组为原数组,并没有进行旋转:    b:如果arry[ind

  • 动态数组C++实现方法(分享)

    回顾大二的数据结构知识.从数组开始.实现了一个可自动扩充容量的泛型数组. 头文件:Array.h #ifndef Array_hpp #define Array_hpp template <class T> class Array{ private: T *base; //数组首地址 int length; //数组中元素 int size; //数组大小,以数组中元素的大小为单位 public: //初始化数组,分配内存 bool init(); //检查内存是否够用,不够用就增加 bool

  • C++ 数据结构线性表-数组实现

    C++ 数据结构线性表-数组实现 线性表的数组实现,实现几个核心的功能,语言是C++,如果有更好的想法和意见,欢迎留言~~~ /* Author : Moyiii * 线性表的数组实现,仅作学习之用,当然如果 * 你想拿去用,随你好啦. */ #include<iostream> using namespace std; //顺序表 class SeqList { public: //构造函数,接受一个默认的列表大小 SeqList(int size = MAX_LIST_SIZE); //析

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

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

  • C++ 中约瑟夫环替换计数器m(数组解决)

    C++ 中约瑟夫环替换计数器m(数组解决) 题目描述: 输入一个由随机数组成的数列(数列中每个数均是大于0的整数,长度已知),和初始计数值m.从数列首位置开始计数,计数到m后,将数列该位置数值替换计数值m,并将数列该位置数值出列,然后从下一位置从新开始计数,直到数列所有数值出列为止.如果计数到达数列尾段,则返回数列首位置继续计数.请编程实现上述计数过程,同时输出数值出列的顺序 比如: 输入的随机数列为:3,1,2,4,初始计数值m=7,从数列首位置开始计数(数值3所在位置) 第一轮计数出列数字为

  • C++算法之在无序数组中选择第k小个数的实现方法

    本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in

  • python 实现在无序数组中找到中位数方法

    一.问题描述 1.求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置.要求:不能使用排序,时间复杂度尽量低 2.例如: lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5 lists = [3, 1, 2] , 中位数为 2 3.算法思想: 利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数

  • Python实现查找数组中任意第k大的数字算法示例

    本文实例讲述了Python实现查找数组中任意第k大的数字算法.分享给大家供大家参考,具体如下: 模仿partion方法,当high=low小于k的时候,在后半部分搜索,当high=low大于k的时候,在前半部分搜索.与快排不同的是,每次都减少了一半的排序. def partitionOfK(numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end

  • 在PHP世界中选择最合适的模板与使用方法第1/2页

    在PHP世界中选择最合适的模板与使用方法第1/2页

    在PHP世界中选择最合适的模板 /google 的广告条--> 事情的起因:你用过FastTemplate吗?对于PHP工程中的模板应用,其实我和我的同事们已经在许多的项目中接触过--关于它的好处,我想无论是在实际开发阶段还是上升到设计模式的角度都已经有很多"前辈先哲"讨论过了.就项目实施而言,在一些中型甚至大型的项目中,有效的将HTML(还有其他文本形式的表现层)和PHP代码分开,不仅在开发阶段可以分别提高界面设计人员和应用程序编写人员的工作效率,更会给项目的测试和维护带来巨大

  • PHP查找数组中只出现一次的数字实现方法【查找特定元素】

    本文实例讲述了PHP查找数组中只出现一次的数字实现方法.分享给大家供大家参考,具体如下: 问题: 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 实现代码如下: <?php function FindNumsAppearOnce($array) { // write code here // return list, 比如[a,b],其中ab是出现一次的两个数字 $count = array_count_values($array); foreach

  • Java中高效判断数组中是否包含某个元素的几种方法

    目录 检查数组是否包含某个值的方法 使用List 使用Set 使用循环判断 使用Arrays.binarySearch() 时间复杂度 使用一个长度为1k的数组 使用一个长度为10k的数组 总结 补充 使用ArrayUtils 完整测试代码 长字符串数据 如何检查一个数组(无序)是否包含一个特定的值?这是一个在Java中经常用到的并且非常有用的操作.同时,这个问题在Stack Overflow中也是一个非常热门的问题.在投票比较高的几个答案中给出了几种不同的方法,但是他们的时间复杂度也是各不相同

  • php实现数组中索引关联数据转换成json对象的方法

    本文实例讲述了php实现数组中索引关联数据转换成json对象的方法.分享给大家供大家参考.具体实现方法如下: public static function encode(&$var) { return '{'.implode(',',self::encodeExcute($var)).'}'; } private static function encodeExcute(&$var) { $json = array(); switch (gettype($var)) { case 'arr

  • php实现多维数组中每个单元值(数字)翻倍的方法

    本文实例讲述了php实现多维数组中每个单元值(数字)翻倍的方法.分享给大家供大家参考.具体分析如下: 前提:一个多维数组,它的每个最小单元值都为数字. 要求:写一个函数,将最小单元值翻倍. 代码如下 <?php $arr = array(1,3,'a'=>20,'b'=>array(2,4,6,'c'=>7)); function arr2($arr){ foreach($arr as $key=>$v){ if(!is_array($v)){ $arr[$key] *= 2

  • JavaScript实现将数组中所有元素连接成一个字符串的方法

    本文实例讲述了JavaScript实现将数组中所有元素连接成一个字符串的方法.分享给大家供大家参考.具体如下: 下面的代码演示了JS中如何通过数组对象的join方法将数组元素连接成一个字符串输出 <!DOCTYPE html> <html> <body> <p id="demo"> Click the button to join the array elements into a string. </p> <butto

  • python 找出list中最大或者最小几个数的索引方法

    如下所示: nums = [1,8,2,23,7,-4,18,23,24,37,2] result = map(nums.index, heapq.nlargest(3, nums)) temp=[] Inf = 0 for i in range(3): temp.append(nums.index(max(nums))) nums[nums.index(max(nums))]=Inf result.sort() temp.sort() print(result) print(temp) 如上,

随机推荐