首页 > 代码库 > Interview-Increasing Sequence with Length 3.
Interview-Increasing Sequence with Length 3.
Given an array, determine whether there are three elements A[i],A[j],A[k], such that A[i]<A[j]<A[k] & i<j<k.
Analysis:
It is a special case of the Longest Increasing Sequence problem. We can use the O(nlog(n)) algorithm, since we only need sequence with length three, we can do it in O(n).
Solution:
1 public static boolean threeIncSeq(int[] A){ 2 if (A.length<3) return false; 3 4 int oneLen = 0; 5 int twoLen = -1; 6 for (int i=1;i<A.length;i++){ 7 //check whether current element is larger then A[twoLen]. 8 if (twoLen!=-1 && A[i]>A[twoLen]) return true; 9 if (twoLen!=-1 && A[i]>A[twoLen] && A[i]<A[oneLen]){10 twoLen = i;11 continue;12 }13 if (twoLen==-1 && A[i]>A[oneLen]){14 twoLen = i;15 continue;16 }17 if (A[i]<A[oneLen]){18 oneLen = i;19 continue;20 }21 }22 23 return false;24 }
Variant:
If we need to output the sequence, we then need to record the sequence of current length 1 seq and length 2 seq.
1 public static List<Integer> threeIncSeq(int[] A){ 2 if (A.length<3) return (new ArrayList<Integer>()); 3 4 int oneLen = 0; 5 int twoLen = -1; 6 List<Integer> oneList = new ArrayList<Integer>(); 7 List<Integer> twoList = new ArrayList<Integer>(); 8 oneList.add(A[0]); 9 for (int i=1;i<A.length;i++){10 //check whether current element is larger then A[twoLen].11 if (twoLen!=-1 && A[i]>A[twoLen]){12 twoList.add(A[i]);13 return twoList;14 }15 if (twoLen!=-1 && A[i]>A[twoLen] && A[i]<A[oneLen]){16 twoLen = i;17 twoList = new ArrayList<Integer>();18 twoList.addAll(oneList);19 twoList.add(A[i]);20 continue;21 }22 if (twoLen==-1 && A[i]>A[oneLen]){23 twoLen = i;24 twoList = new ArrayList<Integer>();25 twoList.addAll(oneList);26 twoList.add(A[i]);27 continue;28 }29 if (A[i]<A[oneLen]){30 oneLen = i;31 oneList = new ArrayList<Integer>();32 oneList.add(A[i]);33 continue;34 }35 }36 37 return (new ArrayList<Integer>());38 39 }
NOTE: This is more compliated then needed, when using List<> in this case, but this idea can be used to print the LIS.
Interview-Increasing Sequence with Length 3.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。