Map of STL takes logarithmic time for insertion. Complexity of this approach reduces to the complexity of sorting. We are still stuck at O(n log n).
We don't have space to store >10^6 ints or bools. With this memory constraint I think O(n log n) is the best solution. Please prove me wrong. On Monday, January 27, 2014, Nishant Pandey <[email protected]> wrote: > I think this the most optimized code i have writen : > > #include <iostream> > #include <vector> > #include <map> > using namespace std; > > int longest_sequence(vector<int> &nums) { > map<int,bool> mp; > int count; > int max = -9999; > int n = 0; > for(unsigned int i = 0; i < nums.size(); i++) { > mp[nums[i]] = true; > } > > for(unsigned int i =0;i<nums.size();i++) { > n = nums[i]; > mp.erase(n); > count = 1; > while(mp.find(n+1)!= mp.end()) { > count++; > mp.erase(n+1); > n++; > } > n = nums[i]; > while(mp.find(n-1)!= mp.end()) { > count++; > mp.erase(n-1); > n--; > } > if(count > max) { > max = count; > } > } > return max; > } > > int main() { > // your code goes here > cout << "Jai Ganesha"; > vector<int> vc; > vc.push_back(5); > vc.push_back(20); > vc.push_back(45); > vc.push_back(3); > vc.push_back(98); > vc.push_back(4); > vc.push_back(21); > vc.push_back(1); > vc.push_back(99); > vc.push_back(2); > cout << endl << longest_sequence(vc); > return 0; > } > > > > NIshant Pandey > Cell : 9911258345 > Voice Mail : +91 124 451 2130 > > > > > On Mon, Jan 27, 2014 at 4:29 PM, Amol Sharma > <[email protected]<javascript:_e({}, 'cvml', '[email protected]');> > > wrote: > >> Given an array of positive numbers arranged in any order. You have to >> find the length of longest continuos(difference of +1, -1) sequence in the >> array. >> >> for eg. >> A[] = *5*, 20, 45, *3*, 98, *4*, 21, *1*, 99, *2* >> >> then longest continuos subsequence is [1, 2, 3, 4, 5] and hence the >> output should be *"5"*, the length of this sequence. >> >> Other Continuos sequence are - >> >> [20, 21] >> [45] >> [98, 99] >> [21] >> >> A[i] can be > 10^6, so hashing is not an option. >> >> Possible Approach is by sorting and time complexity will be O(nlogn). >> >> Does anyone have better approach for this ? >> >> >> >> -- >> Thanks and Regards, >> Amol Sharma >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected] <javascript:_e({}, >> 'cvml', 'algogeeks%[email protected]');>. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected] <javascript:_e({}, > 'cvml', 'algogeeks%[email protected]');>. > -- Dadhaniya Jekin http://about.me/jekin -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
