递归和动态规划——无序数组中的最长连续序列

Posted on | In ,

题目：给定无序数组，返回其中最长的连续序列的长度。
例：
arr=[100,4,200,1,3,2]，最长的连续序列为[1,2,3,4]，所以返回4。

实现：利用哈希表实现时间复杂度O(N)，额外空间复杂度O(N)的方法。

  1. 生成哈希表Hashmap<Integer,Integer> map，key代表遍历过的某个数，value代表key这个数所在的最长连续序列的长度。同时map还可以表示arr的一个数是否出现过。
  2. 从左到右遍历arr。在map中加入记录（arr[i],1），表示arr[i]单独作为一个连续序列。然后看map中是否有arr[i]-1如果有，则arr[i]-1所在的序列可以和arr[i]合并，合并后记为A序列。利用map可以得到A序列的长度lenA，最小值记为leftA，最大值记为rightA。在map中更新与leftA和rightA有关的记录，更新成（leftA,lenA）和（rightA,lenA）。接下来看map中是否含有arr[j]+1,如果有，则说明arr[i]+1所在的序列可以和A合并，合并后记为B序列。利用map得到B序列的长度lenB，…
  3. 遍历过程中使用全局变量max记录每次合并出的序列的长度的最大值，最后返回max。

HashMap的key-value更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.HashMap;
public class LongestConsecutive {
	/**
	 * 利用HashTable更新最长连续子序列的长度
	 * @param arr 原数组
	 * @return 最长连续子序列的长度
	 */
	public int longestConsecutive(int[] arr) {
		if (arr == null || arr.length == 0) {//数组索引为空，或数组对象为空
			return 0;
		}
		int max = 1; //初始化最长连续子序列的长度
		HashMap<Integer, Integer> map = new HashMap<>();
		//遍历数组，如果数组中不包含此元素，则放入map中。
		//注意是一个一个地方放，讨论完一个再放
		for (int i = 0; i < arr.length; i++) {
			map.put(arr[i], 1); //初始化
			if (map.containsKey(arr[i] - 1)) {
				max = Math.max(max, merge(map, arr[i-1], arr[i]));
			}
			if (map.containsKey(arr[i] + 1)) {
				max = Math.max(max, merge(map, arr[i], arr[i] + 1));
			}
		}
		return max;
	}
	/**
	 * 返回合并后连续子序列的长度
	 * @param map
	 * @param i 前一个需要合并的子序列
	 * @param j 后一个需要合并的子序列
	 * @return
	 */
	private int merge(HashMap<Integer, Integer> map, int i, int j) {
		// 合并连续数组，并更新数组的第一个元素和最后一个元素的value值为合并后的数组长度
		int left = i - map.get(i) + 1; //获得i子序列的最小值 （i序列最左边元素）
		int right = j + map.get(j) - 1; //获得j子序列的最大值（j序列最右边元素）
		int len = right - left + 1; //合并后连续子序列的长度
		map.put(left, len);
		map.put(right, len);
		return len;
	}
	public static void main(String[] args) {
		LongestConsecutive lc = new LongestConsecutive();
		int[] arr = {-11, 4, 200, 1, 2, 3};
		System.out.println(lc.longestConsecutive(arr));
	}
}
/***
 *      ┌─┐       ┌─┐ + +
 *   ┌──┘ ┴───────┘ ┴──┐++
 *   │                 │
 *   │       ───       │++ + + +
 *   ███████───███████ │+
 *   │                 │+
 *   │       ─┴─       │
 *   │                 │
 *   └───┐         ┌───┘
 *       │         │
 *       │         │   + +
 *       │         │
 *       │         └──────────────┐
 *       │                        │
 *       │                        ├─┐
 *       │                        ┌─┘
 *       │                        │
 *       └─┐  ┐  ┌───────┬──┐  ┌──┘  + + + +
 *         │ ─┤ ─┤       │ ─┤ ─┤
 *         └──┴──┘       └──┴──┘  + + + +
 *                神兽保佑
 *               代码无BUG!
 */
/***
 * ░░░░░░░░░░░░░░░░░░░░░░░░▄░░
 * ░░░░░░░░░▐█░░░░░░░░░░░▄▀▒▌░
 * ░░░░░░░░▐▀▒█░░░░░░░░▄▀▒▒▒▐
 * ░░░░░░░▐▄▀▒▒▀▀▀▀▄▄▄▀▒▒▒▒▒▐
 * ░░░░░▄▄▀▒░▒▒▒▒▒▒▒▒▒█▒▒▄█▒▐
 * ░░░▄▀▒▒▒░░░▒▒▒░░░▒▒▒▀██▀▒▌
 * ░░▐▒▒▒▄▄▒▒▒▒░░░▒▒▒▒▒▒▒▀▄▒▒
 * ░░▌░░▌█▀▒▒▒▒▒▄▀█▄▒▒▒▒▒▒▒█▒▐
 * ░▐░░░▒▒▒▒▒▒▒▒▌██▀▒▒░░░▒▒▒▀▄
 * ░▌░▒▄██▄▒▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒
 * ▀▒▀▐▄█▄█▌▄░▀▒▒░░░░░░░░░░▒▒▒
 * 单身狗就这样默默地看着你，一句话也不说。
 */