软件工程师面试技巧之使用哈希表降复杂度

JustYY.com 小赖子的英国生活和资讯

7 years ago

最近在刷题,倒不是为了找工作,主要是为了练练脑子,日子过得太舒服,人脑不动容易变笨.

程序员应该都了解并能熟悉使用 Hash 哈希表,哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N).我们来看一道简单的面试题:

给定一个数组,找出相差为2的数对,比如:

{1, 3, 5, 6, 9}
输出为: (1, 3), (3, 5)

拿到这题的时候第一感觉是暴力是否可行? 暴力搜索复杂度为 O(N²), 大概代码如下:

1
2
3

for i = 0 to len - 1
  for j = i + 1 to len
     if abs(arr[i] - arr[j]) = 2) then print_pair_at(i, j)

for i = 0 to len - 1
  for j = i + 1 to len
     if abs(arr[i] - arr[j]) = 2) then print_pair_at(i, j)

有没有更快的方法呢?答案是有的, 我们可以使用哈希表保存数组里的值,然后再第二遍查找的时候看看是不是已经在表里, 如:

for i in arr:
  put i in hash table
for i in arr:
  if hash table contains (i - 2) then print(i, i - 2)
  if hash table contains (i + 2) then print(i, i + 2)

for i in arr:
  put i in hash table
for i in arr:
  if hash table contains (i - 2) then print(i, i - 2)
  if hash table contains (i + 2) then print(i, i + 2)

以上就变成了 O(N) 的算法.

另: 再次推荐一下这本书, 我从AMAZON买的,花了26英镑, 很值.