转载

面试算法题之递增三元组子序列

给出一个无序的整数序列，返回是否存在递增的三元组子序列。如果存在 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 两个变量之中，第三个最大数只和第二个存储变量进行对比即可。

原文 http://navyblue.top/article/170

正文到此结束