找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1454|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Longest Consecutive Sequence】-【刷题第一弹】

[复制链接]

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
发表于 10-23-2014 04:47 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 qiuchen 于 10-23-2014 04:50 PM 编辑

leetcode通道:   https://oj.leetcode.com/problems/longest-consecutive-sequence/

题目:
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)复杂度内完成,一般的排序是不能使用了。这里选择hash来处理题目

1. 建立hash表存储<num,index>
2  对每一个num,从左到右扫描 num vector
   i 检查num-1是否在map中(loop)
   ii 检查num+1 是否在map中(loop)
3  扫描的时候记录sequence的长度

复杂度:O(n)

代码:

  1.        int longestConsecutive(vector<int> &num) {  
  2.             unordered_map<int, int> hashmap;            
  3.             for(int i =0; i< num.size(); i++)  
  4.             {  
  5.                  hashmap[num[i]] = i;  
  6.             }  
  7.             vector<int> visited(num.size(), 0);  
  8.             int maxV = INT_MIN;  
  9.             for(int i =0; i< num.size(); i++)  
  10.             {  
  11.                  if(visited[i]==1) continue;  
  12.                  visited[i]=1;  
  13.                  int len = 1;  
  14.                  int index = num[i]-1;  
  15.                  while(hashmap.find(index) != hashmap.end())  
  16.                  {  
  17.                       visited[hashmap[index]] =1;  
  18.                       index--;  
  19.                       len++;  
  20.                  }  
  21.                  index = num[i]+1;  
  22.                  while(hashmap.find(index) != hashmap.end())  
  23.                  {  
  24.                       visited[hashmap[index]] =1;  
  25.                       index++;  
  26.                       len++;  
  27.                  }  
  28.                  if(len > maxV)  
  29.                       maxV = len;  
  30.             }  
  31.             return maxV;  
  32.        }  
复制代码



本帖被以下淘专辑推荐:

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-10-2014 11:23 PM | 显示全部楼层
  1. public int longestConsecutive(int[] num) {
  2.         if(num==null || num.length==0) return 0;
  3.         if(num.length==1) return 1;
  4.         HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
  5.         int maxLen = 0;
  6.         for(int i=0; i<num.length; i++){
  7.             if(!map.containsKey(num[i])){
  8.                 int up = num[i]+1;
  9.                 int down = num[i]-1;
  10.                 if(map.containsKey(up)){
  11.                     while(map.containsKey(up))
  12.                         up = Math.max(up+1, map.get(up).get(1));
  13.                 }
  14.                 if(map.containsKey(down)){
  15.                     while(map.containsKey(down))
  16.                         down = Math.min(down-1, map.get(down).get(0));
  17.                 }
  18.                 ArrayList<Integer> tmp = new ArrayList<Integer>();
  19.                 tmp.add(down+1);
  20.                 tmp.add(up-1);
  21.                 map.put(num[i], tmp);
  22.                 maxLen = Math.max(maxLen, up-down-1);
  23.             }
  24.         }
  25.         return maxLen;
  26.     }
复制代码

这题考察的是one pass 外加 尽可能少的循环,所以可以用hashmap记忆每次出现数的上下界,并且保证每次计算上届,下届时不会死循环, 所以有 up = Math.max(up+1, map.get(up).get(1)); 这类操作
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表