1 //  2 //题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。  3   4 //思路一：先找到第K个大的数，如何找到任意第K大的数？  5 //首先利用快排思想，先随机的选取一个枢轴，然后进行快速排序分成2部分(左边都小于，后面都大于)，最后得到其下标。  6 //然后利用递归思想，将左边快速排序，将右边快速排序  7 //--------Partiton思想时间复杂度O（n）--------------  8 class Solution   9 { 10 public: 11     void swap(vector
     
       &array, int start, int end) 12     { 13         int tmp = array[start]; 14         array[start] = array[end]; 15         array[end] = tmp; 16     } 17     int Partition(vector
      
        &input,  int start, int end) 18     { 19          20         int pv = input[start]; 21         //int tmp; 22         while(start < end) 23         { 24             while ((start < end) && pv < input[end]) 25             { 26                 end--; 27             } 28             //tmp = input[start]; 29             //input[start] = input[end]; 30             //input[end] = tmp; 31             swap(input, start, end); 32             while ((start < end) && pv >= input[start]) 33             { 34                 start++; 35             } 36             //tmp = input[start]; 37             //input[start] = input[end]; 38             //input[end] = tmp; 39             swap(input, start, end); 40         } 41         return start; 42     } 43 public: 44     vector
       
         GetLeastNumbers_Solution(vector
        
          input, int k)  45     { 46         int len = input.size(); 47         if (len <= 0 || k <=0 ||input.size() < k ) 48         { 49             return {}; 50         } 51         int start = 0; 52         int end = len-1; 53         int index = Partition(input,start, end); 54         while(index != k-1) 55         { 56             if (index > k-1) 57             { 58                 end = index -1; 59                 index = Partition(input,start, end); 60             } 61             else 62             { 63                 start = index+1; 64                 index = Partition(input,start, end); 65             } 66         } 67         vector
         
           tmpVec(input.begin(), input.begin() + k); 68         return tmpVec; 69     } 70  71 }; 72 //调试程序中出现的问题： 73 //首先做交换函数定义的时候，参数要是引用类型void swap(vector
          
            &array, int start, int end) 74 //第二个，就是快排的时候，做交换swap(input, start, end); 75 //第三个，快排的枢轴选取为int pv = input[start]; 76 //第四个，数组中任意第K大的数字 77 // 找任意的第K大的数字，就要想到快排。 78 // int index = Partition(array[], n, int start, int end); 79 // while(index != K-1) 80 // { 81 // if(index > k-1) 82 // { 83 // end = index-1; 84 // Partition(array[],n, start, end); 85 // } 86 // else 87 // { 88 // start = index+1; 89 // Partition(array[], n, start, end); 90 // } 91 // } 92 // 第五个，使用vector容器的时候，添加元素的时候，不要总是使用push_back(); 93 // 还可以使用迭代器， 94 // 例如：vector
           
             tmpVec(input.begin(), input.begin() + k); 95 96 //------------采用时间复杂度O(nlogk)的算法，特别适合处理海量数据 97 //思路：我们可以创建一个大小为K的数据容器来存储最小的K个数字，接下来我们每次从输入的N个整数中读入一个数。 如果容器中已有数字少于K个，则直接把这次读入的整数放入容器中；如果容器中已有K个数字了，就是容器已满， 此时我们不能再插入新的数字而只能替换已有的数字。找出这已有K个数字中的最大值，然后拿这次带插入的整数和最大值进行比较。 如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大， 那么这个数不可能是最小的K个整数之一，于是就抛弃这个整数。 98 //操作如下： 99 //1、在K个整数中找到最大数；100 //2、有可能在这个容器中删除最大数；101 //3、有可能要插入一个新的数字。102 //如果用一个二叉树来实现这个数据容器，那么我们能在O(logk)时间内实现操作。因此对于n个输入数字而言，总的时间效率就是O(nlogk)103 104 //常识：想到二叉树来解决问题，就要想到用什么二叉树为好？105 //如该题就是每次都需要找到K个整数中最大的数字，很容易想到最大堆。在最大堆中，根节点的值总是大于它的子树中任意结点的值。106 //最大堆常识--在O(1)得到已有的K个数字中的最大值，但需要O(logk)时间完成删除和插入操作。107 108 //也可以用红黑树来代替最大堆来实现容器。红黑树通过把结点分为红黑两种颜色并根据一些规则确保树在一定程度上是平衡的，从而保证在红黑书中查找、删除和插入都只需要O(logk)时间。109 //------------------红黑树：multiset集合利用仿函数改变排序顺序时间复杂度O（nlogk）-----110 class Solution 111 {112 typedef multiset
            

> intset;113 typedef multiset