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.
- Total Accepted: 95921
- Total Submissions: 267760
- Difficulty: Hard
- Contributors: Admin
to see which companies asked this question
如果允许$O(n \log n)$的复杂度，那么可以先排序，可是本题要求$O(n)$。
由于序列里的元素是无序的，又要求$O(n)$，首先要想到用哈希表。
用一个哈希表 {unordered_map<int, bool> used}记录每个元素是否使用，对每个元素，以该元素为中心，往左右扩张，直到不连续为止，记录下最长的长度。
1 // Leet Code, Longest Consecutive Sequence 2 // 时间复杂度O(n)，空间复杂度O(n) 3 class Solution { 4 public: 5 int longestConsecutive(const vector &num) { 6 unordered_map used; 7 8 for (auto i : num) used[i] = false; 9 10 int longest = 0;11 12 for (auto i : num) {13 if (used[i]) continue;14 15 int length = 1;16 17 used[i] = true;18 19 for (int j = i + 1; used.find(j) != used.end(); ++j) {20 used[j] = true;21 ++length;22 }23 24 for (int j = i - 1; used.find(j) != used.end(); --j) {25 used[j] = true;26 ++length;27 }28 29 longest = max(longest, length);30 }31 32 return longest;33 }34 }; | 67 / 67 test cases passed. | Status: Accepted |
| Runtime: 26 ms |
1 // Leet Code, Longest Consecutive Sequence 2 // 时间复杂度O(n)，空间复杂度O(n) 3 // Author: @advancedxy 4 class Solution { 5 public: 6 int longestConsecutive(vector &num) { 7 unordered_map map; 8 int size = num.size(); 9 int l = 1;10 for (int i = 0; i < size; i++) {11 if (map.find(num[i]) != map.end()) continue;12 map[num[i]] = 1;13 if (map.find(num[i] - 1) != map.end()) {14 l = max(l, mergeCluster(map, num[i] - 1, num[i]));15 }16 if (map.find(num[i] + 1) != map.end()) {17 l = max(l, mergeCluster(map, num[i], num[i] + 1));18 }19 }20 return size == 0 ? 0 : l;21 }22 23 private:24 int mergeCluster(unordered_map &map, int left, int right) {25 int upper = right + map[right] - 1;26 int lower = left - map[left] + 1;27 int length = upper - lower + 1;28 map[upper] = length;29 map[lower] = length;30 return length;31 }32 };
1 class Solution { 2 public: 3 int longestConsecutive(vector &num) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 7 priority_queue Q; 8 for (int i = 0; i < num.size(); i++) { 9 Q.push(num[i]);10 }11 int ret = 1;12 int maxlen = 1;13 int temp = Q.top();14 Q.pop();15 while (!Q.empty()) {16 if (temp - 1 == Q.top()) {17 temp -= 1;18 maxlen += 1;19 } else if (temp != Q.top()) {20 temp = Q.top();21 maxlen = 1;22 }23 Q.pop();24 ret = max(maxlen, ret);25 }26 return ret;27 }28 };29 30 // O(n) solution31 32 class Solution {33 public:34 int longestConsecutive(vector &num) {35 unordered_map longest;36 int result = 0;37 38 for (int i = 0; i < num.size(); i++) {39 if (longest[num[i]] != 0) {40 continue;41 }42 43 int leftbound = longest[num[i]-1];44 int rightbound = longest[num[i]+1];45 int bound = leftbound + rightbound + 1;46 47 longest[num[i]] = bound;48 longest[num[i]-leftbound] = bound;49 longest[num[i]+rightbound] = bound;50 51 if (result < bound) {52 result = bound;53 }54 }55 return result;56 }57 };
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include // sort 9 #include //greater () model10 using namespace std;11 12 class Solution {13 public:14 vector ::iterator vii;15 set ::iterator sii;16 int longestConsecutive(vector & nums) {17 int ret = 1;18 int result = 0;19 sort(nums.begin(), nums.end(), less ());20 21 for (vii = nums.begin(); vii != nums.end();) {22 int tmp;23 tmp = *vii;24 int next = *++vii;25 if(tmp == next){26 //++vii;27 continue;28 }29 if((tmp+1) != next){30 if(result < ret){31 result = ret;32 }33 ret = 1;34 continue;35 }else {36 ret++;37 }38 }39 /*40 set si;41 //copy(nums.begin(), nums.end(), std::back_inserter(si));42 copy(nums.begin(), nums.end(), si.begin());43 //sort(nums.begin(), nums.end(), less ());44 45 for (sii = si.begin(); sii != si.end();) {46 int tmp;47 tmp = *sii;48 int next = *++sii;49 if((tmp+1) != next){50 if(result < ret){51 result = ret;52 }53 ret = 0;54 continue;55 }else if(tmp == next){56 continue;57 }else {58 ret++;59 }60 }*/61 if(result < ret){62 result = ret;63 }64 return result;65 }66 };67 68 int main() {69 //int arr[] = {9,1,4,7,3,-1,0,5,8,-1,6};70 int arr[] = { 2,0,1,0,1};71 int len = sizeof(arr)/sizeof(arr[0]);72 vector nums(arr, arr+len);73 Solution s;74 cout << s.longestConsecutive(nums) <
| 67 / 67 test cases passed. | Status: Accepted |
| Runtime: 16 ms |
哈希map是一种关联容器，通过键值和映射值存储元素。允许根据键值快速检索各个元素。
插入数据使用 insert方法，查找则使用find方法，find方法返回unordered_map的iterator,如果返回为end()表示未查找到，否则表示查找到。boost::unordered_map是计算元素的Hash值，根据Hash值判断元素是否相同。所以，对unordered_map进行遍历，结果是无序的。