🌕 215. 数组中的第K个最大元素

难度: 🌕

问题描述

---

解法 1 - 变形快排

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 思路：
        // method 1 : 变形快排
        int len = nums.length;
        // 目标：
        // 找到升序排列下 index = len - k - 1 的元素值
        int index = len - k;
        mySol(nums, 0, len - 1, index);
        return nums[index];
    }

    private void mySol(int[] nums, int left, int right, int index) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        // left < right
        int monitor = nums[left]; // 基准值
        int i = left;
        int j = right;
        while(i < j) {
            while(i < j && nums[j] >= monitor) {
                j --;
            }
            while(i < j && nums[i] <= monitor) {
                i ++;
            }
            swap(nums, i, j);
        }
        swap(nums, left, i);
        // 判断继续快排哪边
        if(i == index) {
            return;
        } else if(i > index) {
            mySol(nums, left, i - 1, index);
        } else {
            mySol(nums, i + 1, right, index);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出 1

---

解法 2 - 大根堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 思路：
        // method 2 - 大根堆
        // 建立大根堆，求升序排列下 index = len - k 的元素
        // 依次取出 [len - 1, len - k + 1] 元素，重新调整堆
        // 此时剩余堆的堆顶元素即为 第 k 大
        int len = nums.length;
        build(nums);
        for(int i = len - 1; i >= len - k + 1; i --) {
            swap(nums, 0, i);
            resize(nums, 0, i - 1);
        }
        return nums[0];
    }

    private void build(int[] nums) {
        int len = nums.length;
        // 遍历，依次放入已建立好的堆中
        for(int i = 1; i < len; i ++) {
            int curIndex = i;
            int parentIndex = (curIndex - 1) >> 1;
            // 判断是否需要上浮
            while(curIndex > 0 && parentIndex >= 0 && nums[curIndex] > nums[parentIndex]) {
                swap(nums, curIndex, parentIndex);
                curIndex = parentIndex;
                parentIndex = (curIndex - 1) >> 1;
            }
        }
    }

    private void resize(int[] nums, int curIndex, int endIndex) {
        int leftIndex = 2 * curIndex + 1;
        int rightIndex = 2 * curIndex + 2;
        // 特殊情况特判
        if(leftIndex > endIndex) {
            return;
        }
        // leftIndex <= endIndex
        // 至少还有一个左孩子
        int maxChildIndex = leftIndex;
        // 找到左右孩子值最大的节点下标
        if(rightIndex <= endIndex) {
            if(nums[rightIndex] > nums[leftIndex]) {
                maxChildIndex = rightIndex;
            }
        }
        // 跟孩子比较是否需要下浮
        if(nums[curIndex] < nums[maxChildIndex]) {
            swap(nums, curIndex, maxChildIndex);
            curIndex = maxChildIndex;
            resize(nums, curIndex, endIndex);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出 2