返回信息流Longest Consecutive Sequence
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_set<int> mp;
int i;
for(i=0;i<num.size();i++)
mp.insert(num[i]);
int max=0;
for(i=0;i<num.size();i++)
{
int sum=1;
if(mp.find(num[i])!=mp.end())
{
mp.erase(num[i]);
int left=num[i]-1;
int right=num[i]+1;
while(mp.find(left)!=mp.end())
{
mp.erase(num[i]);
left--;
sum++;
}
while(mp.find(right)!=mp.end())
{
mp.erase(num[i]);
right++;
sum++;
}
}
if(sum>max)
max=sum;
}
return max;
}
};
上述代码超时，如果将while部分写成函数形式，则不会超时，这是为什么呢？
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_set<int> map;
int n = num.size();
for(int i = 0;i < n; ++i){
map.insert(num[i]);
}
int max = 1;
for(int i = 0; i< n; ++i){
if(map.find(num[i]) != map.end()){
int temp = 1;
int cur = num[i];
map.erase(cur);
temp += getCount(map, cur + 1, true);
temp += getCount(map, cur - 1, false);
max = temp > max ? temp : max;
}
}
return max;
}
int getCount(unordered_set<int> &map, int cur, bool asc){
int count = 0;
while(map.find(cur) != map.end()){
map.erase(cur);
count ++;
if(asc)
cur++;
else
cur--;
}
return count;
}
};
如果把函数拆分成两个，用时更少
int findleft(unordered_set<int> &mp,int cur){
int count=0;
while(mp.find(cur)!=mp.end())
{
count++;
mp.erase(cur);
cur--;
}
return count;
}
int findright(unordered_set<int> &mp,int cur){
int count=0;
while(mp.find(cur)!=mp.end())
{
count++;
mp.erase(cur);
cur++;
}
return count;
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #83525同步于 2014/10/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
leetcode oj超时问题。
SoloPerTe
2014/10/21镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
两个写法功能不大一样，
第一种里19行和25行 mp.erase(num[i]);
你确定是num[i]，不是left和right吗？
这个题有个复杂度低点的解法，供参考。
int longestConsecutive(vector<int> &num) {
unordered_map<int, int> m;
int ret = 0, cnt, left, right;
for (int i = 0; i < num.size(); ++i)
{
int x = num[i];
if (m[x]) continue;
m[x] = 1;
left = m[x - 1];
right = m[x + 1];
cnt = left + 1 + right;
m[x - left] = cnt;
m[x + right] = cnt;
if (cnt > ret) ret = cnt;
}
return ret;
}
【 在 SoloPerTe 的大作中提到: 】
: Longest Consecutive Sequence
: [code=c]
: class Solution {
: ...................
确实写错了。。。。改过来之后不超时了。但是比写成函数的形式执行时间要长，为什么呢
【 在 gaoweiwei 的大作中提到: 】
: 两个写法功能不大一样，
: 第一种里19行和25行 mp.erase(num[i]);
: 你确定是num[i]，不是left和right吗？
: ...................
确实做过测试吗？建议拿个长点的序列多测几次试试，不要用leet上那个时间，不是很准。
【 在 SoloPerTe 的大作中提到: 】
: 确实写错了。。。。改过来之后不超时了。但是比写成函数的形式执行时间要长，为什么呢