题目：

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

分析：

给定一个数组，求该数组中的数字所能构成的最长连续数列的长度。要求时间复杂度为O(n)。

我们使用HashMap。其中key为数组中的数字；value为该数字作为某个连续数列的边界时，该数列的长度。例如，对于数列{1,2,3,4,5}，该数列的边界时1和5，那么在HashMap中1和5对应的value都是该数列的长度5。

当我们新读取一个数字时，该数字可能和其左侧或右侧的某个连续数列连接在一起。通过读取HashMap中 n-1 和 n+1 对应的value即可获得左侧和右侧连续数列的长度。之后将它们连接在一起，构成了一个新的更长的数列。最后将新数列边界元素的value更新为新的长度即可。

Continue reading LeetCode #128 Longest Consecutive Sequence→

题目：

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

分析：

给定一个数组，每个数代表该位置上的长条的高度，由此得到一个类似地形图的东西。凹进去的地方可以蓄水，问一共能存多少水。

每一个坑（凹进去的地方）都是由左右2个长条围成的。能存多少水取决于这2个长条中最短的那个。因此，我们对数组进行2次遍历。第1次从左向右，获得该位置左侧最高长条的高度；第2次从右向左，获得该位置右侧最高长条的高度。现在每个位置都知道了它所在的坑被围成的左右2个长条的高度，取较短的那个，就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。

Continue reading LeetCode #42 Trapping Rain Water→

题目：

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

分析：

找出数组中所有出现次数超过总数1/3的元素。

这类问题有一个很经典的算法叫做BM多数投票算法（Boyer-Moore Majority Vote algorithm），时间复杂度O(n)，空间复杂度O(1)。大体思路就是使用一个变量来计数当前出现次数最多的元素X。如果你发现了一个不等于X的数Y，那么计数变量减一。例如，如果数组中有5个X和4个Y，那么可以说X比Y多（5-4）个，或者说有4个X被Y抵消了。想进一步了解该算法的话，请参考http://goo.gl/64Nams。

对于这道题，我们要找到是出现次数大于总数1/3的数，符合要求的数可以能有0个、1个、2个。我们可以在BM多数投票算法的基础上稍作改动，使用2个计数变量即可。其他原理是一样的。需要注意的是，在一轮“抵消”的过程结束后，我们只能保证此时得到的这2个元素是数量最多的，但不见得就超过了总数的1/3。因此，我们还要再分别对这两个数进行一次计数，看它们出现的次数是不是超过了1/3。

Continue reading LeetCode #229 Majority Element II (BM多数投票算法)→