LeetCode[300] Longest Increasing Subsequence

blankyao 发布于2019-08-14 15:01 / 3132人阅读

摘要：再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。保证升序相等也要替换这个值

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 + 替换

复杂度
O(NlgN),O(N)

思路
因为要找increasing的序列，所以先遍历数组。再用二分法找当前值应该在排好序的数组中的插入位置。

对于排好序的数组，尽量用较小的值去替换已经排好序的数组中的值。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。

代码

// 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;
        // 说明这个数字是新加进去这个数组的
        if(len == index) len ++;
    }
    return len;
}

// 相当于在left-right的区间内找到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;
}

服务器托管云服务器 Increasing Subsequence Longest LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65239.html

[LeetCode] 300. Longest Increasing Subsequence

Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7...

luckyyulin 2019-08-19 11:13 评论0 收藏0
leetcode 300. Longest Increasing Subsequence

摘要：题目要求找到整数数组中最长的递增子数组。该子数组可以为不连续的。如题目中例子所示，得到的最长子数组为。最后我们还需要遍历一遍全部子数组的长度并获得最大的长度。题目要求 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [...

eechen 2019-08-15 14:44 评论0 收藏0
leetcode-300-Longest Increasing Subsequence

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。本质：找出最长的递增子序列的长度，可以是不连续的。用一个数组存储递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。成立的理由：每一个数添加以后，都有对...

amc 2019-07-30 17:36 评论0 收藏0
[leetcode]Longest Increasing Subsequence

摘要：对于一个递增子序列，想要增加它的长度，就必须在尾部添加一个更大的值。表示以结尾的最长递增序列的长度。长度增加的条件就是一个数字比大。长度最大值即为输入数组的长度。 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10,...

wow_worktile 2019-08-14 16:52 评论0 收藏0
Longest Increasing Subsequence

摘要：题目链接主要两种方法和用，就是每次找出为结尾的最长的串的长度就好了。所以分解成就是，这个复杂度是。用一个数组，表示的长度为，表示长度为的，最右边的可能的最小值。这里只要求长度即可，那就直接用就可以了，整个用个数组就行了。 Longest Increasing Subsequence 题目链接：https://leetcode.com/problems... 主要两种方法：dp和gree...

FullStackDeveloper 2019-08-14 17:23 评论0 收藏0