专栏首页code秘密花园《剑指offer》最小的k个数

《剑指offer》最小的k个数

本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法,也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解,请后台留言,喜欢请点个好看,谢谢阅读。

题目

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

思路

1.把前k个数构建一个大顶堆

2.从第k个数开始,和大顶堆的最大值进行比较,若比最大值小,交换两个数的位置,重新构建大顶堆

3.一次遍历之后大顶堆里的数就是整个数据里最小的k个数。

代码

    function GetLeastNumbers_Solution(input, k) {      if (k > input.length) {        return [];      }      createHeap(input, k);      for (let i = k; i < input.length; i++) {        // 当前值比最小的k个值中的最大值小        if (input[i] < input[0]) {          [input[i], input[0]] = [input[0], input[i]];          ajustHeap(input, 0, k);        }      }      return input.splice(0, k);    }
    // 构建大顶堆    function createHeap(arr, length) {      for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {        ajustHeap(arr, i, length);      }    }
    function ajustHeap(arr, index, length) {      for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {        if (i + 1 < length && arr[i + 1] > arr[i]) {          i++;        }        if (arr[index] < arr[i]) {          [arr[index], arr[i]] = [arr[i], arr[index]];          index = i;        } else {          break;        }      }    }

本文分享自微信公众号 - code秘密花园(code_mmhy),作者:ConardLi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》11.链表中倒数第k个节点

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • es6类和继承的实现原理

    javascript使用的是原型式继承,我们可以通过原型的特性实现类的继承, es6为我们提供了像面向对象继承一样的语法糖。

    ConardLi
  • 【算法专栏】从上到下打印二叉树

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    ConardLi
  • Java实现快速排序

    用户2436820
  • 剑指offer - 最小的k个数 - JavaScript

    题目描述:输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。

    心谭博客
  • 每个java初学者都应该搞懂的问题

    用户1112962
  • Java六大问题你都懂了吗?

    这些问题对于认真学习java的人都要必知的,当然如果你只是初学者就没必要那么严格了,那如果你认为自己已经超越初学者了,却不很懂这些问题,请将你自己重归初...

    用户2192970
  • 数据分析之微信好友

    周六了,各位周末快乐,今日我们来一文数据分析,从0说起,一起来看pyecharts的作用以及其他相关库的使用!

    公众号guangcity
  • 搭建ELK日志分析系统

    ELK Stack 是Elasticsearch、Logstash、Kiban三个开源软件的组合。在实时数据检索和分析场合,三者通常是配合共用,而且又都先后归于...

    菲宇
  • 数据分析-Pandas DataFrame的连接与追加

    今天我们学习多个DataFrame之间的连接和追加的操作,在合并DataFrame时,您可能会考虑很多目标。例如,您可能想要“追加”它们,您可能会添加到最后,基...

    亚乐记

扫码关注云+社区

领取腾讯云代金券