您现在的位置是:首页 > 正文

《漫画算法2》源码整理-7 第K大的数字

2024-01-30 20:35:38阅读 0

第K大的数字

public class KthLargestNumber {
    /**
     * 寻找第k大的元素
     * @param array  待调整的堆
     * @param k  第几大
     */
    public static int findKthLargestNumber(int[] array, int k) {
        //1.用前k个元素构建最小堆
        buildHeap(array, k);
        //2.继续遍历数组,和堆顶比较
        for (int i = k; i < array.length; i++) {
            if (array[i] > array[0]) {
                array[0] = array[i];

                downAdjust(array, 0, k);
            }
        }
        //3.返回堆顶元素
        return array[0];
    }

    /**
     * 构建堆
     * @param array  待调整的堆
     * @param length  堆的有效大小
     */
    private static void buildHeap(int[] array, int length) {
        // 从最后一个非叶子结点开始,依次下沉调整
        for (int i = (length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, length);
        }
    }

    /**
     * 下沉调整
     * @param array     待调整的堆
     * @param index    要下沉的结点
     * @para

网站文章