Leetcode口试经典150题-128.最长一连序列

解法都在代码里，不懂就留言大概私信
理论上提交这个就是最优解

2. class Solution {
3.     /**解题思路：定义一个hash表用来保存以某个数字结尾的有多少个连续的数
4.     刚开始初始化hash表是把整个数组过一遍，然后记录所有数对应的value（以当前数结尾的最长连续序列）都是1
5.     当我们遍历到某个数字num的时候，如果hash表里能找到num-1的记录就用这个记录的value+1放回hash表
6.     如果没有找到num-1的记录，就记录为，如果找到了就把当前数的value存到hash表里记录value为num-1的value+1
7.     但是这种方法要求先排序(O(N*logN))，虽然提交是可以成功的，但是题目确实要求了O(N)的时间复杂度*/
8.     public int longestConsecutiv2(int[] nums) {
9.         if(nums == null || nums.length == 0) {
10.             return 0;
11.         }
12.         /**就一个数当然是1 */
13.         if(nums.length == 1) {
14.             return 1;
15.         }
16.         /**其他的情况我们先排序 */
17.         Arrays.sort(nums);
18.         /**定义map用于存放某个数字结尾的连续序列的长度 */
19.         Map<Integer,Integer> countMap = new HashMap<>();
20.         countMap.put(nums[0],1);
21.         /**从1位置开始遍历*/
22.         for(int i = 1; i < nums.length; i++) {
23.             countMap.put(nums[i], countMap.getOrDefault(nums[i]-1,0)+1);
24.         }
25.         int max = 0;
26.         for(int num : countMap.values()) {
27.             max = Math.max(max, num);
28.         }
29.         return max;
30.     }
31.     /**第二种解法，个人理解应该是最优解了，解法思路是：使用两个map
32.     一个用来存放以某个数字结尾的map有多长，我们命名为tailMap
33.     一个用来存放以某个数字开头的map有多长，我们命名为headMap
34.     每进来一个数num，先看看以num-1结尾的在tailMap里有没有记录，如果有把它的长度+1作为当前num在tail里的记录，同时记录开始的数字是几
35.     如果没有的话，记录一条以num为key，value为1的记录代表以当前num结尾的最长连续序列长度是1
36.     然后看看headMap里有没有以num+1开头的，如果有，则取出num在tail里的记录和head里的num+1的记录合并，记录起点和终点
37.     比如分别是start和end，那在tailmap里记录end结束的集合，在headMap里记录start开始的记录*/
38.     public int longestConsecutive(int[] nums) {
39.         if(nums == null || nums.length == 0) {
40.             return 0;
41.         }
42.         /**就一个数当然是1 */
43.         if(nums.length == 1) {
44.             return 1;
45.         }
46.         /**定义两个map 一个用来存放以某个数字结尾的map有多长，我们命名为tailMap
47.         一个用来存放以某个数字开头的map有多长，我们命名为headMap */
48.         Map<Integer,Integer> tailMap = new HashMap<>();
49.         Map<Integer,Integer> headMap = new HashMap<>();
50.         for(int num : nums) {
51.             /**这里一定不要忘了，如果出现重复的数字肯定会让结果变得不正确，因为我们map只put了没有删除
52.             所以一定不要重复处理 */
53.             if(tailMap.containsKey(num)) {
54.                 continue;
55.             }
56.             /**我们先处理tailMap，如果有num-1就把值加1，否则使用1（0+1） */
57.             tailMap.put(num, tailMap.getOrDefault(num - 1, 0) + 1);
58.             /**拿到以num结尾的长度 */
59.             int tailLen = tailMap.get(num);
60.             /**找到以num结尾的长度为tailLen的开始的数 */
61.             int tailStart = num - tailLen + 1;
62.             /**先把num放入tailMap */
63.             tailMap.put(num, tailLen);
64.             /**如果headMap里有num+1开头的，把以num结尾的和以num+1的串成一个  */
65.             if(headMap.containsKey(num + 1)) {
66.                 /**拿到以num+1开头的长度 */
67.                 int headLen = headMap.get(num + 1);
68.                 /**拿到以num+1开头的长度为headLen的结尾的数 */
69.                 int headEnd = num + 1 + headLen -1;
70.                 /**分别把这个串起来的区间的头和尾分别存入headMap和tailMap里，长度是整个区间的长度tailLen + headLen */
71.                 tailMap.put(headEnd, tailLen + headLen);
72.                 headMap.put(tailStart, tailLen + headLen);
73.             } else {
74.                 /**如果没有把已num为结尾，以tailLen为长度的开始位置存入headMap */
75.                 headMap.put(tailStart, tailLen);
76.             }
77.         }
78.         int max = 0;
79.         /**最后遍历tailMap找最大长度，这里遍历headMap也是一样的 */
80.         for(int len : tailMap.values()) {
81.             max = Math.max(max,len);
82.         }
83.         return max;   
84.     }
85. }

复制代码

但是某网站的数据比力二*，不想说啥，N*longN的解凌驾50%以上的人
O(N)的解凌驾这么点人？？