c********p
发帖数: 1969 | 1 我觉得我的方法已经很简单了，还是过不了大oj，咋回事呢！
求好方法。
我的方法是，
1,先把整个数组过一遍，放到hashtable里，O(N)
2,再过一遍整个数组，每读到一个数 k，记录hashtable里数字的个数，check是否有比
k大的，如果有，查是否有比这个更大的，并从hashtable删掉这个数，直到没有连续比
它大的了，stop。
check是否有比k小的，如果有，查是否有比这个更小的，并从hashtable删掉这个数，
直到没有连续比它大的了，stop。
删掉k，
查hashtable的个数，差别就是连续的个数。
－－－所以这一步一共也是过了2遍。。。
O(N)
总的时间复杂度也是 O(N)
可是，过不了大oj。。。
咋回事呢？ |
s*********t
发帖数: 52 | 2 你说的查hashtable的个数，因为非空bucket不是连续排列的，所以这个操作的复杂度
是O（M），M是bucket的个数，这个耗时比O（N）还大，我试了一下你说的方法，没有
查剩余数字的个数差，而是数删掉的数字的数量，可以通过大数据，我这里用的是set
，find的复杂度实际上是O(log_n)，也能通过大数据，如果换成unordered_set，会更
快。
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
set myset;
int ret = -INT_MAX;
for (int i = 0; i < num.size(); i++) {
if (myset.find(num[i]) == myset.end()) {
myset.insert(num[i]);
}
}
while (myset.begin() != myset.end()) {
int cntafter = 0, cntbefore = 0;
set::iterator it = myset.begin();
while (myset.find(*it + cntafter + 1) != myset.end()) {
myset.erase(*it + cntafter + 1);
cntafter++;
}
while (myset.find(*it - cntbefore - 1) != myset.end()) {
myset.erase(*it - cntbefore - 1);
cntbefore++;
}
myset.erase(*it);
ret = max(ret, cntbefore + cntafter + 1);
}
return ret;
}
}; |
w******j
发帖数: 185 | 3 public static int longestConsecutive(int[] num) {
Hashtable ht = new Hashtable();
int max = 0;
for(int i = 0; i < num.length; i++)
{
int tmp = num[i];
if(!ht.containsKey(tmp))
{
int low = tmp;
int high = tmp;
ht.put(tmp, new Interval(high, low));
if(ht.containsKey(tmp - 1))
{
low = ht.get(tmp - 1).low;
}
if(ht.containsKey(tmp + 1))
{
high = ht.get(tmp + 1).high;
}
//update only the high and the low
ht.get(low).high = high;
ht.get(high).low = low;
max = Math.max((high - low + 1), max);
}
}
return max;
} |
k*******t
发帖数: 144 | 4 class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_map mapping;
for(int i = 0; i < num.size(); ++i)
{
mapping[num[i]] = true;
}
int longest = 0;
for(int i = 0; i < num.size(); ++i)
{
int len = 0;
int cur = num[i];
while(mapping.find(cur) != mapping.end())
{
++len;
mapping.erase(cur);
++cur;
}
cur = num[i] - 1;
while(mapping.find(cur) != mapping.end())
{
++len;
mapping.erase(cur);
--cur;
}
if(len > longest)
{
longest = len;
}
}
return longest;
}
}; |
c********p
发帖数: 1969 | 5 谢谢好心人指出问题所在！
我按你说的试试:)
set
【在 s*********t 的大作中提到】
: 你说的查hashtable的个数，因为非空bucket不是连续排列的，所以这个操作的复杂度
: 是O（M），M是bucket的个数，这个耗时比O（N）还大，我试了一下你说的方法，没有
: 查剩余数字的个数差，而是数删掉的数字的数量，可以通过大数据，我这里用的是set
: ，find的复杂度实际上是O(log_n)，也能通过大数据，如果换成unordered_set，会更
: 快。
: class Solution {
: public:
: int longestConsecutive(vector &num) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
|
c********p
发帖数: 1969 | 6 我按你说的count了每次删掉的个数，还是不行哦。。。
怎么办，，，能帮我看一下代码么。。。
谢谢！
set
【在 s*********t 的大作中提到】
: 你说的查hashtable的个数，因为非空bucket不是连续排列的，所以这个操作的复杂度
: 是O（M），M是bucket的个数，这个耗时比O（N）还大，我试了一下你说的方法，没有
: 查剩余数字的个数差，而是数删掉的数字的数量，可以通过大数据，我这里用的是set
: ，find的复杂度实际上是O(log_n)，也能通过大数据，如果换成unordered_set，会更
: 快。
: class Solution {
: public:
: int longestConsecutive(vector &num) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
|
