Leetcode 128. Longest Consecutive Sequence (cpp)

题目

解法1：排序

class Solution {
    
public:int longestConsecutive(vector<int>& nums) {
    if(nums.empty()){
    return 0;}sort(nums.begin(),nums.end());int ans = 1, curr = 1;int prev = nums[0];for(int i=1;i<nums.size();i++){
    if(nums[i] == prev){
    continue;}else if(nums[i] - prev == 1){
    curr += 1;ans = max(ans,curr);prev = nums[i];}else{
    prev = nums[i];curr = 1;}}return ans;}
};

解法2：hashtable

class Solution {
    
public:int longestConsecutive(vector<int>& nums) {
    if(nums.empty()){
    return 0;}unordered_map<int,int> seen;for(auto num:nums){
    seen[num] = 1;}int ans = 0;int curr_num;int curr_len;for(auto num : nums){
    // num -1 not in seen, means we have found a number that can use as the start of a new sequenceif(seen.find(num-1) == seen.end()){
    curr_num = num;curr_len = 1;// extend the sequence to the endwhile(seen.find(curr_num+1) != seen.end()){
    curr_num += 1;curr_len += 1;}ans = max(ans,curr_len);}}return ans;}
};

这个解法乍看是O(n^2),实际上while循环里面一共的操作次数是n。因为我们首先判断了num-1是不是有出现，没有出现意味着当前的num作为一个新序列开始，我们随后进行while循环遍历这个序列。而在while循环被遍历过的数字，随后便不会再进while循环

解法3：hashtable

这种解法利用两个while循环，第一个while循环遍历所有大于等于2的sequence，第二个while循环跳过所有的没有出现的数字。这样做的时间复杂度是O(K)的，K = max(nums) - min(nums)。这样来看应该比解法2慢，因为k>=n，n为数组长度，只有数字全部连续时，k等于n

class Solution {
    
public:int longestConsecutive(vector<int>& nums) {
    if(nums.empty()){
    return 0;}int min_num = INT_MAX;int max_num = 0;unordered_map<int,int> seen;for(auto num:nums){
    seen[num] = 1;min_num = min(min_num,num);max_num = max(max_num,num);}int ans = 1;int curr = 1;int num = min_num;while(true){
    // while the next number appeared in nums, we keep updating the num and the countwhile(seen.find(num+1) != seen.end()){
    num += 1;curr += 1;// cout << num << endl;}ans = max(ans,curr);// if the current number is equal to the max number in nums, means we have ended hereif(num == max_num) break;// use this while loop to skip all the nums that not appeared in numswhile(seen.find(num+1) == seen.end()){
    num += 1;}curr = 0;}return ans;}
};