下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 11 | 面试题:返回数据流中的第K大元素
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18891
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享

精选留言(30)

  • 2018-11-08
    把这个课程推荐给朋友,他今天跟我说,他去今日头条面试,3个算法题有2个在这里出现,一个是这道。一个是之前 两个数和 的问题,还要当场写代码~
    25
  • 2018-10-15
    老师,这边第一种情况(使用数组的情况),因为数组本身是排好的,是不是只对新元素进行插排的效果会比使用快排的效果更好?
    2
    11
  • 2018-10-15
    后续会讲一下AVL嘛
    5
  • 2018-10-22
    对数的概念
    https://wenku.baidu.com/view/29e2e92bef06eff9aef8941ea76e58fafab04511.html
    时间复杂度的底数
    https://blog.csdn.net/bengxu/article/details/80320546
    我已经忘光了.....
    展开
    2
  • 2018-10-16
    遇到过流式数据找中值的面试,最好能给讲解下。
    1
    2
  • 2019-01-08
    上面那个Go语言的有问题,他不能保证一直都是满足小顶堆的限制的,因为push的时候调用的是自己的方法而不是堆的方法,所以不会检测。下面是我写的
    type IntHead []int
    func (i IntHead) Len() int { return len(i)}
    func (In IntHead) Less(i ,j int) bool {
        return In[i] < In[j]}
    func (In IntHead) Swap(i, j int) {
        In[i], In[j] = In[j], In[i]
    }
    func (In *IntHead) Push(x interface{}) {
        *In = append(*In, x.(int))
    }
    func (In *IntHead) Pop() interface{} {
        old := *In
        n := len(old)
        x := old[n -1]
        *In = old[0:n-1]
        return x
      
    }
    type KthLargest struct {
        K int
        H *IntHead
    }


    func Constructor(k int, nums []int) KthLargest {
        min := &IntHead{}
        
        heap.Init(min)
        kth := KthLargest{K:k, H:min}
        for _, num := range nums {
            kth.Add(num)
        }
        return kth
    }


    func (this *KthLargest) Add(val int) int {
        if this.H.Len() == 1 && (*this.H)[0] == 0 && val == -1 {
             min := &IntHead{-1,0}
             heap.Init(min)
            this.H = min
        }
        if this.H.Len() < this.K {
            heap.Push(this.H, val)
        } else if (*this.H)[0] < val {
            heap.Pop(this.H)
        heap.Push(this.H, val)
        }
        return (*this.H)[0]
    }

    }
    展开

    作者回复: 赞👍🏻

    1
  • 2018-10-30
    这个题面试真遇到过,当时回答的也是 维护一个 k 长度的数组,每次加入都进行排序,先跟最小的比,如果比最小的都小就直接抛弃.比最小的大就挨个与数组中元素比较. 时间复杂度是 n*k

    作者回复: 你提议的算法就是相对比较简单朴素的算法,O(n*k) 速度太慢,必须要 O(n) 的算法才能通过面试的。

    1
  • 2018-10-21
    老师随机选择也可以介绍下? 会比堆更优的吧
    1
  • 2018-10-11
    小顶堆这个思路有点巧妙,前人是怎么想出来的
    1
  • 2019-11-09
    PHP 最小堆实现第K大元素
    class MinHeap extends SplHeap
    {
        //用最小堆存储第K大元素
        public function compare( $value1, $value2 ) {
            return ( $value2 - $value1 );
      }
    }
    class KthLargest {
        public $k;
        public $heap;
        /**
         * @param Integer $k
         * @param Integer[] $nums
         */
        function __construct($k, $nums) {
            $this->k = $k;
            $this->heap = new MinHeap();
            foreach($nums as $num)
            {
                $this->add($num);
            }
        }
      
        /**
         * @param Integer $val
         * @return Integer
         */
        function add($val) {
            if($this->heap->count()<$this->k){
                $this->heap->insert($val);
            }else{
                if($val>$this->heap->top()){
                    $this->heap->insert($val);
                    $this->heap->extract();
                }
            }
            return $this->heap->top();
        }
    }
    展开

    作者回复: nice

  • 2019-09-20
    老师那个构造函数有点问题,可改为(仅供参考):
    ```
    public KthLargest(int k, int[] nums) {
            this.k = k;
            heap = new PriorityQueue<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (i < k) {
                    heap.offer(nums[i]);
                    continue;
                }
                else {
                    if (nums[i] > heap.peek()) {
                        heap.poll();
                        heap.offer(nums[i]);
                        continue;
                    }
                }
            }
        }
    ```
    展开
  • 2019-05-24
    平时都用c#,居然不自带优先队列数据结构
  • 2019-04-27
    老师,第一个使用排序的方案,效率不应该是nklogk,而应该是nk+klogk, 这了排序使用链表进行一次排序后,以后直接就是有序数组不断插入,并且删除头就行,不需要排序了
  • 2019-03-11
    https://docs.python.org/2/library/heapq.html python 原生的heapq.nlarges() 在leetcode 上运行时超时,请问是本身优化的不好吗?
  • 2019-03-03
    这连着几道题了。用PHP做了好几天,也没做出来。
  • 用数组来做 每次新进一个数都是在已经排好序的K个数中插入一个新的数所以整体的时间复杂度应该是n*k?
  • 为何我用老师的Java代码copy到leetcode去通过不了……
  • 2019-01-18
    老师,这题python该怎么实现, Leecode中好像不支持import queue,该怎么办?
  • 2019-01-12
    老师,学习课程时,是不是不推荐使用不支持heap的语言,比如c?否则精力花在自己实现heap上,没有必要。

    作者回复: 不用自己去实现,对的,建议选用高级语言,自己实现的heap,特别是二插堆,性能比较有限。

  • 2018-12-21
    今天看到一个算法测试题,讲到了优先级队列,大顶堆和小顶堆,而且我还通过课程的理解讲给了同事,竟然给他讲明白了,很有成就感

    作者回复: 👍🏻赞