Use bitwise hashmap.
On Thu, Jan 30, 2014 at 8:46 PM, Don <[email protected]> wrote: > No. If you start at any number in a sequence it will find the entire > sequence. There is no need to start again at some other number in that > sequence. > > Don > > > On Wednesday, January 29, 2014 12:19:21 AM UTC-5, Varun Sachdeva wrote: > >> If we don't process the same number more than once, does it not create a >> situation when we miss out on the solution? >> For example the digit 6 in this sequence: >> 1,2,3,4,0,2,3,1,4,5,2,4,3,4,5,6,7,8,9 >> >> Varun >> >> >> Varun Sachdeva >> >> >> >> On 28 January 2014 00:29, Don <[email protected]> wrote: >> >>> This works, and I think is O(N*log(N)) which is similar to sorting and >>> scanning. >>> >>> An unordered map will be faster, in general. It could be made faster in >>> most cases by looping over items left in the map, to avoid processing the >>> same number more than once. Also, when the number of items left in the map >>> is less than max, there is no need to continue because you know they can't >>> form a sequence longer than max. >>> >>> int longest_sequence(vector<int> &nums) >>> { >>> unordered_map<int,bool> mp; >>> int max = 0; >>> for(unsigned int i = 0; i < nums.size(); i++) >>> mp[nums[i]] = true; >>> >>> while(mp.size() > max) >>> { >>> int i; >>> int n = mp.begin()->first; // Pick first item in map >>> mp.erase(n); >>> int count = 1; >>> for(i = n+1; mp.contains(i); ++i) >>> { >>> ++count; >>> mp.erase(i); >>> } >>> for(i = n-1; mp.contains(i); --i) >>> { >>> ++count; >>> mp.erase(i); >>> } >>> >>> if (count > max) max = count; >>> } >>> >>> return max; >>> } >>> >>> >>> >>> On Monday, January 27, 2014 9:17:56 AM UTC-5, Nishant Pandey 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]>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]. >>>>> >>>> >>>> -- >>> 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]. >>> >> >> -- > 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]. > -- 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].
