讨论/题目交流/面试题 17.14. 最小K个数 这题用快排找前 arr[0,k-1],为什么以arr[k]分界。emmm/
面试题 17.14. 最小K个数 这题用快排找前 arr[0,k-1],为什么以arr[k]分界。emmm

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        int left = 0, right = arr.size() -1;
        while(left != k) {
            int pivot = arr[left];
            int low = left, high = right;
            while(low < high) {
                while(low < high && arr[high] >= pivot)
                    --high;
                arr[low] = arr[high];
                while(low < high && arr[low] <= pivot)
                    ++low;
                arr[high] = arr[low];
            }
            arr[low] = pivot;
            if(low == k)
                left = low;
            else if(low > k)
                right = low - 1;
            else
                left = low + 1;
        }
        return  vector<int>(arr.begin(),arr.begin() + k);
    }
};
展开讨论
hayami🌸发起于 2020-05-11
最近编辑于 2020-05-11
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        if(len==0){
            return new int[0];
        }else if(len<=k){
            return arr;
        }
      return  quicklySort(arr,0,len-1,k);
    
    }

    private int[] quicklySort(int[] arr, int left, int right,int k) {
       
        while(left < right){
          int  index=partition(arr,left,right);
          if(index > k-1) right = index-1;
          if(index < k-1) left = index+1;
          if(index == k-1) break;

    }
    return Arrays.copyOf(arr,k);
}

    private int partition(int[] arr, int left, int right) {
        
        int base = arr[left];
        while (left<right){
            while (left<right&&arr[right]>=base){
                right--;
            }
            arr[left] = arr[right];
            while (left<right&&arr[left]<=base){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left]=base;
        return left;
    }
}

1
展开全部 3 讨论