The document says Dictionary is implemented as a hash table. 1
Essentially you are doing the same thing as HashMap magic.
The document says Dictionary is implemented as a hash table. 1
Essentially you are doing the same thing as HashMap magic.
Idea is very simple.
Step 1 is O(n) time and step 2 is O(1) time, and the space is O(1), because the maximum size of the array is INT_MAX-INT_MIN, which is a constant.
However, this requires a little too much memory in practice. To handle small vectors better, we should split the vector into several vectors with smaller range (<=MAX_RANGE), and put the result together later. To combine the results of two vectors, we need a little more information, e.g. the length of consecutive numbers including the maximum number.
Time and space complexity doesn't change by this. With splitting, the sum of the numbers of elements in the two vectors is the same as the number of elements of the original vector. Splitting itself costs O(n) time. The maximum number of splitting is O(1), (INT_MAX-INT_MIN)/MAX_RANGE.
This is O(n) time algorithm both in average and in worst time.
#include <algorithm>
#include <cmath>
class Solution {
public:
const int MAX_RANGE = 65535;
int longestConsecutive(vector<int>& nums) {
int a[5];
longestConsecutiveAll(nums,a,a+1,a+2,a+3,a+4);
return a[0];
}
void longestConsecutiveAll(vector<int>& nums, int* any, int* at_min, int* at_max, int* max, int *min){
// any : length of longest consecutive numbers
// at_min : length of longest consecutive numbers which contain the minimum
// at_max : length of longest consecutive numbers which contain the maximum
// max : maximum
// min : minimum
*max = *(max_element(nums.begin(),nums.end()));
*min = *(min_element(nums.begin(),nums.end()));
long long lmax=*max, lmin = *min;
if(lmax-lmin>=MAX_RANGE){
int border = (*max+*min)/2;
vector<int> first_half, second_half;
for(auto i:nums)
if(i<border) first_half.push_back(i);
else second_half.push_back(i);
int any_[2], at_min_[2], at_max_[2], max_[2], min_[2];
longestConsecutiveAll(first_half,&any_[0],&at_min_[0],&at_max_[0],&max_[0],&min_[0]);
longestConsecutiveAll(second_half,&any_[1],&at_min_[1],&at_max_[1],&max_[1],&min_[1]);
if(max_[0]+1==min_[1]){ //when first_half and second_half are next to each other by,
//longest consecutive numbers can span between them
*any=std::max(std::max(any_[0],any_[1]),at_max_[0]+at_min_[1]);
if(any_[0]==max_[0]-min_[0]+1) //when first_half is all consecutive
*at_min=at_min_[1]+any_[0];
else
*at_min=at_min_[0];
if(any_[1]==max_[1]-min_[1]+1) //when second_half is all consecutive
*at_max=at_max_[0]+any_[1];
else
*at_max=at_max_[1];
}else{
*any=std::max(any_[0],any_[1]);
*at_max=at_max_[1];
*at_min=at_min_[0];
}
return;
}
vector<char> n(*max-*min+1,0);
for(auto i:nums){
n[i-*min]=1;
}
int longest=0;
bool is_first=true;
int current=0;
for(auto i:n){
if(i){
current++;
}else{
if(is_first)*at_min=current;
current=0;
is_first=false;
}
if(current>longest) longest=current;
}
*at_max=current;
*any=longest;
return;
}
};