LeetCode 215. Kth Largest Element in an Array（数组中的第K个最大元素）Java实现

这道题一开始我做的实现，自然而然想到了用快排的思想，去找最大的这个元素
这题我一开始用的办法是

private int quickSort(int[] nums, int left, int right, int k) {
    int partitionIndex = partition(nums, left, right);
    if (partitionIndex == k) {
        return nums[k];
    } else if (partitionIndex < k) {
        return quickSort(nums, partitionIndex + 1, right, k);
    } else {
        return quickSort(nums, left, partitionIndex - 1, k);
    }
}

但是发现，使用这种快排的方式，居然没有java自带的Array.sort，排序后再选取元素快，居然用了近50ms，这有点让我匪夷所思

后来看了3ms的代码发现问题出在基准数的处理上
导致快排慢的原因是我的基准数选取有问题，我选取基准数的策略是
每次选取最后一个数字当基准数
这种策略在数组元素升序较多的情况下性能比较糟糕
总言之，这个策略在测试的数据中选取了很差的基准数，导致程序变慢了

改进：采用三数取中选取基准值
不从数组的最后一个元素取基准值，而是从数组的开头，中间，结尾的三个值比较出一个中值，然后以它作为基准值

实现方法：

private int medianOf3(int[] nums, int left, int right) {
    int mid = left + (right - left) / 2;
    if (nums[left] > nums[mid]) {
        swap(nums, left, mid);
    }
    if (nums[left] > nums[right]) {
        swap(nums, left, right);
    }
    if (nums[mid] > nums[right]) {
        swap(nums, mid, right);
    }
    return mid;
}

然后把我们的递归形式改成递推的形式，这一步优化也很重要

private int quickSort(int[] nums, int left, int right, int k) {
    while(true) {
        if (left == right) {
            return nums[left];
        }
        int mid = medianOf3(nums, left, right);
        int partitionIndex = partition(nums, left, right, mid);
        if (partitionIndex == k) {
            return nums[k];
        } else if (partitionIndex < k) {
            left = partitionIndex + 1;
        } else {
            right = partitionIndex - 1;
        }
    }
}

完整代码：

package medium._215;

/**
 * @author zmj
 * @create 2019/1/5
 */
public class Solution {
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private int medianOf3(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        if (nums[left] > nums[mid]) {
            swap(nums, left, mid);
        }
        if (nums[left] > nums[right]) {
            swap(nums, left, right);
        }
        if (nums[mid] > nums[right]) {
            swap(nums, mid, right);
        }
        return mid;
    }

    private int partition(int[] nums, int left, int right, int mid) {
        int pivot = nums[mid];
        swap(nums, mid, right);
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] < pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, right, i);
        return i;
    }

    private int quickSort(int[] nums, int left, int right, int k) {
        while (true) {
            if (left == right) {
                return nums[left];
            }
            int mid = medianOf3(nums, left, right);
            int partitionIndex = partition(nums, left, right, mid);
            if (partitionIndex == k) {
                return nums[k];
            } else if (partitionIndex < k) {
                left = partitionIndex + 1;
            } else {
                right = partitionIndex - 1;
            }
        }
    }

    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, nums.length - k);
    }
}

程序执行时间: