Java O(nlogn) solution


  • 0
    L

    Have an ArrayList to store the result.
    Algorithm:
    for x in given array:
    If arraylist is empty or x > last number of arraylist:
    add x to arraylist
    else
    binary search arraylist to find the first one >= x.
    replace it with x.

    Time: O(nlogn). n is looping through give array. logn is binary search

    public class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums.length < 2)
                return nums.length;
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (list.isEmpty()) {
                    list.add(nums[i]);
                    continue;
                }
                int last = list.get(list.size() - 1);
                if (nums[i] > last) {
                    list.add(nums[i]);
                } else {
                    int pos = find(list, nums[i]);
                    list.set(pos, nums[i]);
                }
            }
            return list.size();
        }
        public int find(ArrayList<Integer> list, int val) {
            int start = 0, end = list.size() - 1;
            if (val < list.get(0))
                return 0;
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (list.get(mid) == val)
                    return mid;
                if (list.get(mid) < val)
                    start = mid + 1;
                else
                    end = mid - 1;
            }
            return start;
        }
    }
    

  • 0
    L

    you can use Arrays.binarySearch :)


Log in to reply
 

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