Sharing my 1ms 0(nlogn) Solution in Java


  • 0
    A

    public class Solution {
    public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) { return 0;}
    int n = nums.length, len = 1;
    int[] result = new int[n];
    result[0] = nums[0];

        for (int i = 1; i < n; i++) {
            int currentElement = nums[i];        
            if (currentElement <= result[0]) { 
                result[0] = currentElement; 
           } else if (currentElement > result[len-1]) {
                result[len++] = currentElement;
            } else {
                int position = binarySearch(result, currentElement, 0, len-1);
                result[position] = currentElement;
            }
        }
        return len;
    }
    
    public int binarySearch(int[] arr, int target, int start, int end) {
        int leftIndex = start, rightIndex = end;
        
        while (rightIndex - leftIndex > 1 ) { 
            int middleIndex = (leftIndex + rightIndex) / 2, middleElement = arr[middleIndex];            
            if (middleElement == target) {
                return middleIndex;
            } else if (middleElement < target) {
                leftIndex = middleIndex;
            } else {
                rightIndex = middleIndex;
            }
        }
        return rightIndex;
    }
    

    }


Log in to reply
 

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