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?
Tip:给定一个无序数组,求出数组中最长的递增子序列的长度。(我原来错误的以为求连续的最长递增子序列长度,但本文并没有要求子序列连续。)
实例化一个与给定数组nums相同长度的数组min来存储递增子序列,并另min[0]=nums[0]。
遍历nums数组,如果后一个元素大于当前元素,min[len++]=nums[i].
否则就从min数组中找到最后一个小于当前元素的位置,并插入到min数组中,(最后一个小于当前元素的后面)。
findPosition函数用来找到插入位置,时间复杂度为O(logn)。
lengthofLIS()遍历整个数组时间复杂度为O(n)
所以整体复杂度为O(nlogn)
package medium; public class L300LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length <= 0)
return 0;
int len = 0;
int[] min = new int[nums.length];
min[len++] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > min[len - 1]) {
min[len++] = nums[i];
} else {
int position = findPosition(min, 0, len - 1, nums[i]);
System.out.println(position);
min[position] = nums[i];
}
}
return len;
} private int findPosition(int[] min, int low, int high, int k) {
// 在min【】中找到k可以换的位置
while (low <= high) {
int mid = low + (high - low) / 2;
if (min[mid] == k) {
return mid;
} else if (min[mid] > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
} public static void main(String[] args) {
L300LongestIncreasingSubsequence l300 = new L300LongestIncreasingSubsequence();
int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
int[] nums1 = { 1, 3, 2 };
int len = l300.lengthOfLIS(nums1);
System.out.println(len);
}
}