40 最小的 K 个数 马上解题
解题思路
大小为 K 的最小堆
复杂度:O(NlogK) + O(K)
特别适合处理海量数据
应该使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素。
维护一个大小为 K 的最小堆过程如下:在添加一个元素之后,如果大顶堆的大小大于 K,那么需要将大顶堆的堆顶元素去除。
代码
41.1 数据流中的中位数 马上解题
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
代码
41.2 字符流中第一个不重复的字符 马上解题
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 "go" 时,第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时,第一个只出现一次的字符是 "l"。
代码
42 连续子数组的最大和 马上解题
题目描述
{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。
代码
43. 从 1 到 n 整数中 1 出现的次数 马上解题 Leetcode : 233. Number of Digit One
代码