最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
java面试算法题之递增三元组子序列
时间:2016-08-15 编辑:简简单单 来源:一聚教程网
给出一个无序的整数序列,返回是否存在递增的三元组子序列。 如果存在 i, j, k 使得 arr[i]即返回true;如果不存在则返回false。
解法一
public static void main(String[] args) {
int[] inputNums = { 6, 4, 3, 2, 4, 7, 1 };
System.out.println(isExist(inputNums));
}
public static boolean isExist(int[] inputNums) {
if (inputNums.length < 2) {
return false;
}
int smallestBefore = inputNums[0];
boolean[] existSmallerArray = new boolean[inputNums.length];
for (int i = 1; i < inputNums.length; i++) {
if (inputNums[i] > smallestBefore) {
existSmallerArray[i] = true;
} else {
smallestBefore = inputNums[i];
}
}
int largestAfter = inputNums[inputNums.length - 1];
for (int i = inputNums.length - 2; i >= 0; i--) {
if (inputNums[i] < largestAfter && existSmallerArray[i]) {
return true;
}
if (inputNums[i] >= largestAfter) {
largestAfter = inputNums[i];
}
}
return false;
}
思路
这道题起先我使用的是暴力破解法,时间耗费的是 O(N3)。如果是需要找递增的二元组的话完全可以使用 O(N)的遍历方法,但是在解题中,第二个数和第三个数进行对比的前提是第二个数大于第一个数,而这个前提又是基于对数组的遍历,所以形成了 O(N3)。
可以想到的优化是第一个循环用来一边遍历一边对比,对比为真时再进入下一个循环,这时的空间复杂度为 O(N2)
如果不想嵌套下一个循环的,可以使用数组将比较完成的状态进行存储。另开一个循环,对比遍历时使用数组中的数据得出结果,这种方法的空间复杂度是O(N)。
解法二
public static boolean isExist2(int[] inputNums){
if(inputNums.length < 3){
return false;
}
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for(int i = 0; i < inputNums.length; i++){
if(inputNums[i] < first){
first = inputNums[i];
continue;
}
if(inputNums[i] > first && inputNums[i] < second){
second = inputNums[i];
continue;
}
if(inputNums[i] > second){
return true;
}
}
return false;
}
思路
保留了此前两个比较状态在 first 和 second 两个变量之中,第三个最大数只和第二个存储变量进行对比即可。
相关文章
- iOS面试中如何优雅回答Block导致循环引用的问题 06-21
- 智联招聘APP如何直约面试 智联招聘直约面试教程 04-17
- Java面试题之基本语法 03-17
- java面试算法题之子序列与最长公共子串 08-15
- java面试题目10个容易出错的地方 05-11
- 一套面试题总结代码 04-02