[LeetCode] 300. Longest Increasing Subsequence

luckyyulin 发布于2019-08-19 11:13 / 1611人阅读

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,101], therefore the length is 4.

Note:

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?

Solution using Arrays.binarySearch(int[] array, int start, int end, int target)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 0;
        //use Arrays.binarySearch() to find the right index of to-be-inserted number in dp[]
        int[] dp = new int[nums.length];
        for (int num: nums) {
            int index = Arrays.binarySearch(dp, 0, len, num);
            if (index < 0) {
                //calculate the right index in dp[] and insert num
                index = -index-1;
                dp[index] = num;
            }
            //if last inserted index equals len, increase len by 1
            //reason: index is 0-based, should always keep: len == index+1
            if (index == len) len++;
        }
    }
}

Define a binary search method

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int index = 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int pos = findPos(dp, nums[i], index);
            if (pos > index) index = pos;
            dp[pos] = nums[i];
        }
        return index+1;
    }
    private int findPos(int[] nums, int val, int index) {
        int start = 0, end = index;
        while (start+1 < end) {
            int mid = start+(end-start)/2;
            if (nums[mid] == val) return mid;
            else if (nums[mid] < val) start = mid;
            else end = mid;
        }
        if (nums[end] < val) return end+1;
        else if (nums[start] < val) return end;
        else return start;
    }
}

GPU云服务器云服务器 Increasing Subsequence Longest LeetCode

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

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

LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。保证升序相等也要替换这个值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 评论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