LeetCode[300] Longest Increasing Subsequence

blankyao 發(fā)布于2019-08-14 15:01 / 3246人閱讀

摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會能保證得到的結(jié)果是最長的。保證升序相等也要替換這個值

LeetCode[300] Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest
increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest
increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
Note that there may be more than one LIS combination, it is only
necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

BinarySearch + 替換

復(fù)雜度
O(NlgN),O(N)

思路
因為要找increasing的序列，所以先遍歷數(shù)組。再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。

對于排好序的數(shù)組，盡量用較小的值去替換已經(jīng)排好序的數(shù)組中的值。因為要找的是最長的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會能保證得到的結(jié)果是最長的。

代碼

// O(NlgN) 
public int lengthOfLIS(int[] nums) {
    int len = 0;
    int[] a = new int[nums.length];
    for(int val : nums) {
        int index = binary(a, 0, len - 1, val);
        a[index] = val;
        // 說明這個數(shù)字是新加進(jìn)去這個數(shù)組的
        if(len == index) len ++;
    }
    return len;
}

// 相當(dāng)于在left-right的區(qū)間內(nèi)找到val的插入位置。保證升序；
public int binary(int[] a, int left, int right, int val) {
    while(left <= right) {
        int mid = getMid(left, right);
        if(a[mid] >= val) {
            right = mid - 1;
        }
        // 相等也要替換這個值;
        else {
            left = mid + 1;
        }
    }
    return left;
}

public int getMid(int left, int right) {
    return left + (right - left) / 2;
}