2020-03-20

1.题目描述

最小的k个数

2.题解

使用冒泡排序即可
使用快排会更快一点

3.代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k==arr.size()) return arr;
        int l=arr.size(),t;
        vector<int>res;
        for (int i=0;i<k;i++){
            for (int j=l-1;j>i;j--){
                if (arr[j-1]>arr[j]){
                    t=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=t;
                }
            }
            res.push_back(arr[i]);
        }
        return res;
    }
};

int main(){
    Solution s;
    vector<int>t={3,5,2,5,2,1},r;
    r=s.getLeastNumbers(t,3);
    for (int i=0;i<r.size();i++){
        cout<<r[i]<<" ";
    }
    cout<<endl;
    return 0;
}

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k==arr.size()) return arr;
        int len=arr.size();
        quicksort(0,len-1,k-1,arr);
        vector<int> res(arr.begin(),arr.begin()+k);
        return res;
    }

    void quicksort(int l,int h,int k,vector<int>& arr){
        if (l>=h) return; // 递归结束
        int index=partition(l,h,arr);
        if (index==k) return;
        else if (index<k) quicksort(index+1,h,k,arr);
        else quicksort(l,index-1,k,arr);
    }

    int partition(int l,int h,vector<int>& arr){
        int value=arr[l];
        while (l<h){
            while (l<h&&arr[h]>value) h--;
            if (l<h) arr[l++]=arr[h];
            while (l<h&&arr[l]<value) l++;
            if (l<h) arr[h--]=arr[l];
        }
        arr[l]=value;
        return l;
    }
};