方法一:sort排序

1.解题思路

题意:
对于给定数组,输出其中最小的k个。
分析:
考察各类排序算法

2.解法

使用c++库函数sort(),从小到大排序后,输出前k个数。

3.具体代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>ans;
        sort(input.begin(),input.end());
        for(int i=0;i<k;i++){
            ans.push_back(input[i]);
        }
        return ans;
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度:,c++中的sort()是改进的快排算法。
空间复杂度:,前k个数,常数级别。

方法二:堆

1.解题思路

堆是一颗完全二叉树,可由向上调整是由空堆,逐个插入元素,来建立初始堆,
或向下调整从n/2的位置,倒着将编号n/2,n/2-1,...,1直到编号为1的结点调成堆

堆排序利用的是完全二叉树,n个结点的完全二叉树,树高log2n,叶子结点的范围是[n/2+1,n](叶子结点中存放小顶堆的最大值或大顶堆的最小值)
在这题目,建立一个大顶堆,取堆顶元素与堆尾交换,令堆长度-1,从根结点开始向下调整即可。

2.解法

堆排序步骤:

  • 初始建堆:从最后一个非叶结点开始,倒序,每次向下调整到叶子结点。
    • 向下调整:对父节点向下与其孩子结点调整(大顶堆父结点与有最大权值的孩子结点交换),从当前结点下调到叶子结点为止
  • 删除根后的重建堆:堆尾覆盖堆首,堆长度-1,向下调整叶子结点。每趟将该数组元素最大值移到末尾。

3.图解

图片说明

4.具体代码

class Solution {
public:
    //对父节点向下与其孩子结点调整,从当前结点下调到叶子结点为止 
    void downadjust(vector<int>&heap,int low,int high){//其中low为欲调整结点的数组下标,high一般为堆的最后一个元素的数组下标
        int i=low,j=i*2;//i为欲调整结点,j为其左孩子 
        while(j<=high){//存在孩子结点 
            if(j+1<=high&&heap[j+1]>heap[j])j=j+1;//左右孩子中最大的下标
            if(heap[j]>heap[i]){//建立大顶堆
                swap(heap[j],heap[i]);
                i=j;//保持i为欲调整结点,j为其左孩子 
                j=i*2;
            }else break;
        }
    } 
    void HeapSort(vector<int>&heap,int n){
        for(int i=n/2-1;i>=0;i--){//建堆,前n/2个是非叶子节点,其余是叶子 
            downadjust(heap,i,n-1);
        }
        for(int i=n-1;i>=0;i--){//交换堆首堆尾,然后令堆元素数量减一 
            swap(heap[0],heap[i]);
            downadjust(heap,0,i-1);
        } 
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        HeapSort(input,input.size()); //堆排序
        for(int i=0;i<k;i++){//取前k个元素
            ans.push_back(input[i]);
        }
        return ans;
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度:,建堆时间复杂度,n个元素,每次维护堆需要
空间复杂度:,仅用存储前k个元素在vector中

方法三:快速排序

1.解题思路

相关知识
快速排序,不稳定,交换类,分治思想
选择任意元素,将其放在了正确位置上(一次划分),然后递归左右。

2.解法

快速排序步骤:

  • 随机选主元,对[left,right] 进行划分

    • srand((unsigned)time(NULL));//生成随机数种子
    • rand()%(b-a+1)+a;//[a,b]内的随机数 ,左右端点相差不超过RAND_MAX (32767)
  • 分区的目的是传入一个数组和选定的一个元素,把所有小于那个元素的其他元素放在左边,大于的放在右边(即将选定的这个元素放在正确的位置)。

    • 具体做法是在枢轴元素右边找一个比其小的,然后移到枢轴元素左边,在枢轴元素左边找一个比其大的,然后移到枢轴元素右边
  • 一次划分确定一个元素的最终位置,直到所有元素排序完成即可。

3.具体代码

class Solution {
public:
    int Partition(vector<int>&A,int left,int right){//分区的目的是传入一个数组和选定的一个元素,把所有小于那个元素的其他元素放在左边,大于的放在右边。
        int p=(int)(round(1.0*rand()/RAND_MAX*(right-left)+left));//生成[left,right]内随机数P,随机选取主元 
        swap(A[p],A[left]);
        int temp=A[left];//选取枢轴元素 
        while(left<right){
            while(A[right]>temp&&left<right)right--;//在枢轴元素右边找一个比其小的,然后移到枢轴元素左边 
            A[left]=A[right];
            while(A[left]<=temp&&left<right)left++;//在枢轴元素左边找一个比其大的,然后移到枢轴元素右边 
            A[right]=A[left];
        }
        A[left]=temp;
        return left; 
    } 
    void quicksort(vector<int>&A,int left,int right){//快速排序,调整序列中枢轴元素的位置,递归 
        if(left<right){
            int pos=Partition(A,left,right);//一次划分确定一个元素的最终位置 
            quicksort(A,left,pos-1);
            quicksort(A,pos+1,right);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        quicksort(input,0,input.size()-1); //快速排序
        for(int i=0;i<k;i++){//取前k个元素
            ans.push_back(input[i]);
        }
        return ans;        
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度:

  • 最好时间复杂度:,无序时;递归树高log2n;每一层的划分总共需要遍历一遍数组(除基准外),近似做n次比较,所以整棵树总需比较nlogn
  • 最坏时间复杂度:,有序时,每次划分只得到一个比上一次划分少一个元素的子数组,递归树深度n,总需比较(n-1)+(n-2)+(n-3)+...+1=n(n-1)/2。
  • 平均时间复杂度:

空间复杂度:

  • 最坏空间复杂度:,划分为一个元素与其他所有元素,递归栈深度为n,所有元素全部入栈
  • 平均空间复杂度: