算法笔记十（计算第I大的数）数据结构与算法

计算第I大的元素
一般的思路是，把所有的数据都排好序，然后就可以求出第I大的数，但是其实这是一种浪费，因为我们只是为了得到第I大的元素，并不需要将数据排序
【算法笔记十（计算第I大的数）】这里采用的方法就是，随机从集合中取出一个数，保证数组左边的数都比它小，右边都比它大(还记得快速排序吗？)
根据这个数的位置K，去跟I做比较，如果等于I，则得出结果，否则第I大的数要么在其左边，要么在其右边，然后去其左边或者右边的区间，递归上述操作

过程：求出随机位置上的数应该出现在已排好序结果集中的最终位置号J
分解：判断j与i的大小，得出第i大的数是在左区间还是右区间，或者就等于J
终止：J == I

代码实现：

#ifndef __p1__GetINumber__ #define __p1__GetINumber__#include #include using namespace std; class GetINumber {public: //生成一个介于a和b之间的一个随机数字 int generateRandomNumber(int a,int b){ if(b == a){ return a; } int number = arc4random()%(b - a); return number + a; }//交换两个元素，采用异或技术 void changeTwoItems(int * data,int i,int j){ if(*(data + i) == *(data + j)){ return; } *(data + i) = *(data + i) ^ *(data + j); *(data + j) = *(data + i) ^ *(data + j); *(data + i) = *(data + j) ^ *(data + i); }//finalDataPosition左边的数据，都比它大，右边都比它小 int solve(int * data,int left,int right,int targetPosition){//随机取一个数字，看下这个数字应该排在第几的位置 int referenceDataPosition = generateRandomNumber(left,right); int referencDataValue = https://www.it610.com/article/*(data + referenceDataPosition); //用来保存该数组最终应该出现的位置 int finalDataPosition = referenceDataPosition; int lp = left,rp=right,direction = -1; while(lp < rp){ if(direction == -1){ //从后往前 for(; rp>=lp; rp--){ if(*(data + rp) >= referencDataValue){ changeTwoItems(data,rp,finalDataPosition); finalDataPosition = rp; direction = 1; break; } } }else{ //从前往后 for(; lp<=rp; lp++){ if(*(data + lp) < referencDataValue){ changeTwoItems(data,lp,finalDataPosition); finalDataPosition = lp; direction = -1; break; } } } }//该数正好排在第targetPosition位上 if(targetPosition - 1== finalDataPosition){ return referencDataValue; } //计算位置时，采用从大到小的排序，所以，第I大的元素，在当前第finalDataPosition大的元素的左边 if(finalDataPosition > targetPosition - 1){ return solve(data,left,finalDataPosition - 1,targetPosition); }else{ //第I大的元素，在当前第finalDataPosition大的元素的右边 return solve(data,finalDataPosition + 1,right,targetPosition); } }//入口，在data数组中，求出第targetPosition大的数字 int doCalculate(int * data, int size, int targetPosition){ if(targetPosition > size){ return *(data + size - 1); } return solve(data,0,size - 1,targetPosition); }}; #endif /* defined(__p1__GetINumber__) */

这里有个交换两个元素大小的一个技巧函数 changeTwoItems，采用XOR方式实现。