Java simple and easy understanding Nlogn solution


  • 5
    J
    public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int[] res = new int[nums.length];
        int len = 0;
        res[len] = nums[0];
        len++;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] < res[0]) {
                res[0] = nums[i];
            }
            else if(nums[i] > res[len - 1]) {
                res[len] = nums[i];
                len++;
            }
            else {
                int index = doBinarySearch(res, 0, len - 1, nums[i]);
                res[index] = nums[i];
            }
        }
        return len;
    }
    private int doBinarySearch(int[] nums, int start, int end, int target) {
        while(start + 1 < end) {
            int mid = start + (end - start)/2;
            if(nums[mid] == target) {
                return mid;
            }
            else if(nums[mid] < target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if(nums[start] == target) {
            return start;
        }
        else {
            return end;
        }
    }
    

    }


  • 0
    H
    This post is deleted!

Log in to reply
 

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