LeetCode 剑指Offer II 119

 

一道水题，我首先想到的做法是暴力的枚举。

class Solution {
public:

int dp[100100],ans = 1;

int longestConsecutive(vector<int>& nums)
{
    int n = nums.size();

    memset(dp,0,sizeof(dp));
    sort(nums.begin(),nums.end());
    dp[0] = 1;

    if(!n)     return 0;
    if(n == 1) return 1;
    cout<<n<<endl;

    for(int i=1;i<n;i++)
       {
           if(nums[i] == nums[i-1] + 1)
             {
                 dp[i] = dp[i-1] + 1;
                 cout<<dp[i]<<" "<<nums[i]<<endl;
                 ans = max(ans,dp[i]);
             }
            
           else if(nums[i] == nums[i-1]) dp[i] = dp[i-1];

                else dp[i] = 1;
       }

    return ans;
}
};

 

打完瞅了一眼正解，官方给出了Hash表的做法。

 

 

class Solution {
public:

int ans = 0;
unordered_set <int > s;

int longestConsecutive(vector<int>& nums)
{
    for(int b:nums)
       s.insert(b);

    for(int num:s)
       if(!s.count(num - 1))
         {
            int current_num = num,current_len = 1;
            while(s.count(current_num + 1))
               {
                  current_num++;
                  current_len++;
               }
            
            ans = max(ans,current_len);
         }

    return ans;
}
};

 

 

 

虽然评论区都说一眼就Hash，但是由于本蒟蒻不会用Set，因此没有想到。如果你想了解Set，请继续读下去。

 

什么是Set？

set是STL 中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现，红黑树的效率要高于二叉树，且插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系，所以效率比较高。

set，顾名思义是 “集合” 的意思，在 set 中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交 (set_intersection), 差 (set_difference) 并 (set_union)，对称差 (set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用 multiset。

  1.头文件：<set>
　2.定义：set<int> q;
　3.输入（插入）：insert(x);
　4.删除指定元素：erase(x);
　5.清空：clear();
　6.判空：empty();
　7.大小：size();
　8.二分查找：q.lower_bound(x);

有趣的一个性质是，set内部维护一个递增序列。并且它具有去重功能，在本题中作用巨大。

#include <iostream>
#include <set>

using namespace std;

set <int > s;

int a[10] = {1,2,50,666,7,2,5,-10,-10,0};
 
int main()
{
    for(int i=0;i<10;i++)
           s.insert(a[i]);
    
    for(set<int >::iterator i = s.begin();i != s.end();i++)
       cout<<*i<<" ";

return 0;
}

输出：-10 0 1 2 5 7 50 666