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