Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given
The longest increasing subsequence is
[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?
Answer:
Method 1: normal dp. Time: O(n*n), Space:O(n).
public class Envelope {
int w;
int h;
public Envelope(int w, int h) {
this.w = w;
this.h = h;
}
@Override
public String toString() {
return "[" + w + "," + h + "]";
}
}
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null)
return 0;
int m = envelopes.length;
if (m == 0)
return 0;
// [2,3],[5,4],[6,4],[6,7]
Comparator<Envelope> cmp = new Comparator<Envelope>() {
@Override
public int compare(Envelope l, Envelope r) {
//ascending order!
if (l.w > r.w) {
return 1;
} else if (l.w == r.w) {
if (l.h > r.h) {
return 1;
} else if (l.h == r.h) {
return 0;
} else {
return -1;
}
} else {
return -1;
}
}
};
Envelope[] list = new Envelope[m];
int[] count = new int[m];
int max = 1;
for (int i = 0; i < m; i++) {
Envelope t = new Envelope(envelopes[i][0], envelopes[i][1]);
list[i] = t;
count[i] = 1;
}
Arrays.sort(list, cmp);
//System.out.print(Arrays.asList(list));
for (int i = 1; i < m; i++) {
for (int j = i - 1; j >= 0; j--) {
if (list[i].w > list[j].w && list[i].h > list[j].h) {
if (count[j] + 1 > count[i]) {
count[i] = count[j] + 1;
}
}
}
if (count[i] > max) {
max = count[i];
}
}
return max;
}
Method 2: dp + binary search! Time: O(n*logn), Space:O(n).
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes==null || envelopes.length==0 || envelopes[0]==null || envelopes[0].length!=2)
return 0;
int m = envelopes.length;
// [2,3],[5,4],[6,7],[6,4]
Comparator<int[]> cmp = new Comparator<int[]>() {
@Override
public int compare(int[] w1, int[] w2) {
if(w1[0] != w2[0]){
return w1[0] - w2[0];
}else{
return w2[1] - w1[1];
}
}
};
Arrays.sort(envelopes, cmp);
int[] dp = new int[m];
int maxLen = 0;
dp[0] = envelopes[0][1];
for (int i = 1; i < m; i++) {
if(envelopes[i][1] > dp[maxLen]){
dp[++maxLen] = envelopes[i][1];
}else{
int index = Arrays.binarySearch(dp,0,maxLen,envelopes[i][1]);
if(index < 0){
index = -(index + 1);
dp[index] = envelopes[i][1];
}
}
}
return maxLen + 1;
}
}
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes==null || envelopes.length==0 || envelopes[0]==null || envelopes[0].length!=2)
return 0;
int m = envelopes.length;
// [2,3],[5,4],[6,7],[6,4]
Comparator<int[]> cmp = new Comparator<int[]>() {
@Override
public int compare(int[] w1, int[] w2) {
if(w1[0] != w2[0]){
return w1[0] - w2[0];
}else{
return w2[1] - w1[1];
}
}
};
Arrays.sort(envelopes, cmp);
int[] dp = new int[m];
int maxLen = 0;
dp[0] = envelopes[0][1];
for (int i = 1; i < m; i++) {
if(envelopes[i][1] > dp[maxLen]){
dp[++maxLen] = envelopes[i][1];
}else{
int index = Arrays.binarySearch(dp,0,maxLen,envelopes[i][1]);
if(index < 0){
index = -(index + 1);
dp[index] = envelopes[i][1];
}
}
}
return maxLen + 1;
}
}
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0)return 0;
int len = nums.length, maxLen=0;
int[] dp = new int[len];
dp[0] = nums[0];
//dp + Binary Search, time: O(n*logn), space: O(n)
for(int i=1; i<len; ++i){
if(nums[i] > dp[maxLen]){
dp[++maxLen] = nums[i];
}else{
int index = Arrays.binarySearch(dp, 0, maxLen, nums[i]);
if(index < 0){
index = -(index+1);
dp[index] = nums[i];
}
}
}
return maxLen + 1;
}
No comments:
Post a Comment