LeetCode: Longest Consecutive Sequence

想到map了，可惜没想到用erase来节省空间，看了网上答案

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int> &num) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         map<int, int> rec;
 7         for (int i = 0; i < num.size(); i++) rec.insert(pair<int, int>(num[i], 1));
 8         int maxcon = 0;
 9         for (int i = 0; i < num.size(); i++) {
10             map<int, int>::iterator it = rec.find(num[i]);
11             if (it != rec.end()) {
12                 int left = num[i]-1;
13                 int right = num[i]+1;
14                 while (1) {
15                     map<int, int>::iterator iter = rec.find(left);
16                     if (iter != rec.end()) {
17                         left--;
18                         rec.erase(iter);
19                     }
20                     else break;
21                 }
22                 left++;
23                 while (1) {
24                     map<int, int>::iterator iter = rec.find(right);
25                     if (iter != rec. end()) {
26                         right++;
27                         rec.erase(iter);
28                     }
29                     else break;
30                 }
31                 right--;
32                 maxcon = max(maxcon, right - left + 1);
33                 rec.erase(it);
34             }
35         }
36         return maxcon;
37     }
38 };

贴上自己写的更加简单的代码

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int> &num) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         map<int, int> S;
 7         int sum = 0;
 8         for (int i = 0; i < num.size(); i++) S[num[i]] = 1;
 9         for (int i = 0; i < num.size(); i++) {
10             if (S.count(num[i])) {
11                 int left = 1;
12                 int tmp = num[i];
13                 while (S.count(tmp-left)) {
14                     S.erase(tmp-left);
15                     left++;
16                 }
17                 int right = 1;
18                 while (S.count(tmp+right)) {
19                     S.erase(tmp+right);
20                     right++;
21                 }
22                 S.erase(tmp);
23                 sum = max(sum, left+right-1);
24             }
25         }
26         return sum;
27     }
28 };

 1 public class Solution {
 2     public int LongestConsecutive(int[] nums) {
 3         Dictionary<int, int> S = new Dictionary<int, int>();
 4         int ans = 0;
 5         for (int i = 0; i < nums.Length; i++) {
 6             if (!S.ContainsKey(nums[i])) S.Add(nums[i], 1);
 7         }
 8         for (int i = 0; i < nums.Length; i++) {
 9             if (S.ContainsKey(nums[i])) {
10                 int left = 1;
11                 int tmp = nums[i];
12                 while (S.ContainsKey(tmp - left)) {
13                     S.Remove(tmp - left);
14                     left++;
15                 }
16                 int right = 1;
17                 while (S.ContainsKey(tmp + right)) {
18                     S.Remove(tmp + right);
19                     right++;
20                 }
21                 S.Remove(tmp);
22                 ans = Math.Max(ans, left + right - 1);
23             }
24         }
25         return ans;
26     }
27 }

View Code