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].
