题目

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。示例1输入[1,3,5,2,2],5,3返回值2

解析

冒泡法

和这篇博客思路类似

K轮冒泡排序~即可

class Finder {
   public:    int findKth(vector
   
     input, int n, int K) {
           // write code here        if(n

res; int j=0,i=0; for(i=0;i

input[j+1]){

swap(input[j],input[j+1]); } } } return input[j]; }};

快排法

主体思路就是利用快速排序每次能将比某个哨兵小的数放在左侧，大的数放在右侧

class Finder {
   public:    int findKth(vector
   
     a, int n, int K) {
           return quickfind(a, 0, n-1, K);    }         int quickfind(vector
    
     & a, int left, int right, int k) {
           int i = left;        int j = right;        int mark = a[left];                 while (i < j) {
               while (i < j && a[j] >= mark)                --j;            if (i < j)                a[i++] = a[j];                         while (i < j && a[i] <= mark)                ++i;            if (i < j)                a[j--] = a[i];        }        a[i] = mark;                 //哨兵右侧比他大的数字个数        int big_num = right - i;                //如果哨兵刚好是第K大的数        if (k - big_num - 1 == 0)            return mark;        else if (k - big_num - 1 > 0) {
               //如果右侧数字个数不够K个，则从左侧找第k-big_num-1大的数            return quickfind(a, left, i - 1, k - big_num - 1);        } else {
               //如果右侧数字个数比K多，则在右侧找第K大的数            return quickfind(a, i + 1, right, k);        }    }};

转载地址：http://ykevi.baihongyu.com/

你可能感兴趣的文章

第三方SDK：百度地图SDK的使用

查看>>

Android studio_迁移Eclipse项目到Android studio

查看>>

JavaScript setTimeout() clearTimeout() 方法

查看>>

CSS border 属性及用border画各种图形

查看>>

转载知乎-前端汇总资源

查看>>