关于快速选择的尾递归

2021-03-25

快速选择通常用于求top k的情况，时间复杂度为O(n)，而空间复杂度由于其存在递归栈深度，为O(logn)，笔者在本文里将递归写法转为迭代法。

首先是递归写法。

class Solution {
    int ret=0;
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length-1,k);
        return ret;
    }
    public void quickSort(int[] nums,int l,int r,int k){
        if(l<=r){
            int pivot=nums[l];
            int i=l,j=r;
            while(i<j){
                while(i<j&&pivot>nums[j])
                    j--;
                if(i<j){
                    nums[i]=nums[j];
                    i++;
                }
                while(i<j&&pivot<nums[i])
                    i++;
                if(i<j){
                    nums[j]=nums[i];
                    j--;
                }
            }
            nums[i]=pivot;
            if(k==i+1)
                ret=pivot;
            else if(k<i+1)
                quickSort(nums,l,i-1,k);
            else
                quickSort(nums,i+1,r,k);
        }
    }
}

可以注意到无论是快排还是快速选择都属于尾递归，因此可用迭代进行如下优化。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l=0,r=nums.length-1;
        while(l<=r){
            int m=quickSort(nums,l,r,k);
            if(m==k-1)
                return nums[m];
            if(m<k-1)
                l=m+1;
            else
                r=m-1;
        }
        return -1;
    }
    public int quickSort(int[] nums,int i,int j,int k){
        int pivot=nums[i];
        while(i<j){
            while(i<j&&pivot>nums[j])
                j--;
            if(i<j){
                nums[i]=nums[j];
                i++;
            }
            while(i<j&&pivot<nums[i])
                i++;
            if(i<j){
                nums[j]=nums[i];
                j--;
            }
        }
        nums[i]=pivot;
        return i;
    }
}

同样的道理，快速排序也可进行迭代法优化，在这里不详述。