/*给定非排序数据找第k大数字练手题*/
/*快排核心算法partition 线性时间找数组第k大的数 */
/*允许改变数组顺序 很多简单的题目但是对时间要求更优化的题目都可以转化成这个知识点*/
class Solution {
public:
    int Partition(vector<int>& arr , int length , int left , int right){
     //传入数组需要能够被改变
     //无效数据处理

     int index = right;//这里可以做一个随机化
     //如果做随机化需要swap(arr[index] , arr[end])
     //arr[end]现在作为哨兵

     int small = left - 1;//比哨兵小的数组的尾指针
     for(index = left ; index < right ;index++){
         if(arr[index] < arr[right]){
             //比哨兵小的情况
             small++;
             if(small != index)
                swap(arr[index] , arr[small]);
         }
     }

     small++;
     swap(arr[small] , arr[right]);
     return small;
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
         int left = 0;
         int right = arr.size() - 1;
         vector<int> ans;

         if(k == 0) return ans;
         if(right < 0) return ans;
         
         int index = Partition(arr , k , left , right);

         while(index != k - 1){
              if(index > k - 1){
                 right = index - 1;
                 index = Partition(arr , k , left , right);
              }
              else {
                 left = index + 1;
                 index = Partition(arr , k - index  -1 , left , right);
              }
         }
         
         for(int i = 0;i < k;i++) ans.push_back(arr[i]);
         return ans;
    }
};