LeetCode 第703题 Kth Largest Element in a Stream 【堆】Java

原题地址:https://leetcode.com/problems/kth-largest-element-in-a-stream/

设计一个类寻找一个数据流里面的第k大的元素。注意是指排序后的第k大元素,而不是第k个不重复元素。

你的KthLargest类应该有一个构建器接受一个整数k和一个整数数组nums,包含流的初始元素。每次调用方法KthLargest.add,返回流里面的第k大的元素。

例子:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

注意: 
你可以假定nums的长度 k-1 而且 k ≥ 1

继续阅读

LeetCode 第378题 Kth Smallest Element in a Sorted Matrix 【堆】java

原题地址:https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

给定一个n x n的矩阵,每一行,每一列都是正序排列,寻找矩阵内的第k小元素。注意是指排序后的第k大元素,而不是第k个不重复元素。

例如:

matrix =
[ [ 1, 5, 9],
[10, 11, 13],
[12, 13, 15] ],
k = 8,

返回 13.

注意,你可以假定k永远合法,1 ≤ k ≤ n2

继续阅读

Leetcode专题 堆结构和堆排序

注意,算法和数据结构里面的堆(Heap)和内存分配里面的堆(Heap)并不是一个概念。内存分配里面的堆的概念更类似于池(Pool)。Stackoverflow上有一个讨论,我们就不细究了。知道我们这里讨论的是算法和数据结构里面的堆就好了。我还是按照《算法导论》的介绍来进行。

所谓堆,就是一个用一维数组来表示一个完全二叉树的这么一个数据结构。所谓二叉树就是一种树,每一个父节点,有最多两个子节点,一般叫做左右子树。

继续阅读

Leetcode 第240题 Search a 2D Matrix II【分而治之】(Java)

原题地址:https://leetcode.com/problems/search-a-2d-matrix-ii/

写一个高效的算法来搜索m*n的矩阵,该矩阵有如下属性:

  • 每行整数从左到右升序排列
  • 每列整数从上到下升序排列

例子:

针对如下矩阵

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

如果目标是5,返回true
如果目标是20,返回false

继续阅读

LeetCode专题 分而治之

这几天我再次调整刷题的策略,目前的策略是重新通读认真学习《算法导论》,我曾经无数次看过算法导论,但是都是通读,而没有进行练习,所以知识根本没有掌握,浮于表面的浮光掠影。算法并不困难,但是需要大量的实操代码才能熟练。这是我以前只看不练的策略最大的问题。

继续阅读