好贷网好贷款

[leetcode] Longest Consecutive Sequence

发布时间:2016-12-3 6:18:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[leetcode] Longest Consecutive Sequence",主要涉及到[leetcode] Longest Consecutive Sequence方面的内容,对于[leetcode] 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)的时间复杂度,其实没有什么特别巧妙的做法,也就是对set容器的使用 int longestConsecutive(vector<int> &num) { unordered_map<int,int> s; int maxlen = 0; for(vector<int>::iterator it = num.begin(); it != num.end(); it++) s[*it] = 1; //each element in the array can be accessed at most twice, //therefore the amortized running time is still o(n). for(vector<int>::iterator it = num.begin(); it != num.end(); it++){ if(s[*it] == 1){ s[*it] = 0; int len = 1; int left = *it - 1; int right = *it + 1; while(s.find(left) != s.end() && s[left]){ s[left--] = 0; len++; } while(s.find(right) != s.end() && s[right]){ s[right++] = 0; len++; } if(maxlen < len) maxlen = len; } } return maxlen; }

上一篇:Android中的各种布局
下一篇:8.21 关于extjs 下拉框联动

相关文章

相关评论