题解 | #最小的K个数#

最小的K个数

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
        if (k == 0) {
            return new ArrayList<>();
        }
        int length = input.length;
        for (int i = length / 2 - 1; i >= 0; --i) {
            adjustHeap(input, i, length);
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = length - 1; i >= 0; --i) {

            int minValue = input[0];
            input[0] = input[i];
            input[i] = minValue;

            result.add(minValue);
            if (result.size() >= k) {
                break;
            }
            adjustHeap(input, 0, i);
        }
        return result;
    }

    private void adjustHeap(int[] array, int parent, int length) {

        int temp = array[parent];
        int child = 2 * parent + 1;

        while (child < length) {

            if (child + 1 < length && array[child] > array[child + 1]) {
                ++child;
            }

            if (temp <= array[child]) {
                break;
            }

            array[parent] = array[child];
            parent = child;
            child = 2 * child + 1;
        }

        array[parent] = temp;
    }

全部评论

相关推荐

07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:20
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务