C++ O(NLogN) time and O(1) space with LIS elements stored in place


  • 0
    M
    #include <algorithm>
    #include <vector>
    using namespace std;
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len = nums.size();
            if (0 == len)return 0;
            int maxLen = 1;
    	    auto begin = nums.begin();
    	    for (int i = 1; i < len; ++i)
    	    {
    		    auto ret = std::lower_bound(begin, begin + maxLen, nums[i]);
    		    if (ret == begin + maxLen)//maxLen + 1
    			    *(begin + maxLen++) = nums[i];
    		    else if (nums[i] < *ret)
    			    *ret = nums[i];
    	    }
    	    return maxLen;
        }
    };

  • 0
    I

    O(N) time? Ridiculous. Do you know about lower_bound?


  • 0
    M

    Thank you for pointing it out. I meant O(NlogN)...I have corrected the title.

    Yes, lower_bound requires logN time to find the element no less than nums[i] in O(logN) time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.