归档 2015

二叉搜索树(BST)相较于哈希表的优势

哈希表支持在Θ(1)时间内完成下列操作:

1) 查找
2) 插入
3) 删除

对于自平衡的二叉搜索树,比如红黑树(Red-Black Tree),平衡二叉树(AVL Tree),伸展树(Splay Tree)等,上述操作的时间复杂度是O(Logn)。

因此对于常用操作哈希表似乎完胜BST。那么我们在什么时候应该选择BST而不是哈希表,BST的优势何在。下面是BST的几项比较重要的优势。

我们只需通过中序遍历BST即可获得排好序的key列表。而这并非哈希表的自然操作,需要额外的工作才可以实现。

使用BST可以很容易地执行顺序统计,找出最接近的最小和最大元素,执行范围查询。像排序一样,这些操作也不是哈希表的自然操作。

BST相较于哈希表更容易实现,我们可以很容易地实现自定义的BST。而要实现哈希表,我们一般需要依赖编程语言提供的库函数。

使用BST,所有的操作都可以确保在O ...

继续阅读

[LeetCode]Rising Temperature

题目描述:

Given a Weather table, write a SQL query to find all dates' Ids with higher temperature compared to its previous (yesterday's) dates.

+---------+------------+------------------+
| Id(INT) | Date(DATE) | Temperature(INT) |
+---------+------------+------------------+
|       1 | 2015-01-01 |               10 |
|       2 | 2015-01-02 |               25 |
|       3 | 2015-01-03 |               20 |
|       4 | 2015-01-04 ...

继续阅读

[LeetCode]Delete Duplicate Emails

题目描述:

Write a SQL query to delete all duplicate email entries in a table named Person, keeping only unique emails based on its smallest Id.

+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
| 3  | john@example.com |
+----+------------------+

Id ...

继续阅读

每月存档

去年

明年