猿问

增加三重态子序列

我正在解决以下问题:


Given an unsorted array return whether an increasing subsequence of length 3 exists in the array or not. Formally return true if there exists i, j, k such that:

arr[i]<arr[j]<arr[k] given 0 <= i < j < k <= n-1


这是我的代码:


public boolean increasingTriplet(int[] nums) {

    if (nums.length < 3) return false;

    for (int i = 0; i < nums.length-2; i++) {

        if (nums[i] < nums[i+1]) {

            if (nums[i+1] < nums[i+2]) return true;

        }

    }

    return false;

}

我的代码在以下输入中失败:


[5,1,5,5,2,5,4] 显然,对于此序列,我的代码应该返回true,但是由于我看不到长度3的任何增加的子序列,所以我无法弄清楚为什么这样做,对于理解此问题的任何帮助,我们将不胜感激。


aluckdog
浏览 192回答 2
2回答

芜湖不芜

public boolean increasingTriplet(int[] nums) {&nbsp; &nbsp; int first=Integer.MAX_VALUE;&nbsp; &nbsp; int second=Integer.MAX_VALUE;&nbsp; &nbsp; int third=Integer.MAX_VALUE;&nbsp; &nbsp; for(int p=0; i<nums.length; p++){&nbsp; &nbsp; &nbsp; &nbsp; if(nums[p]<=third){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; third=nums[p];&nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(nums[p]<=second){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; first=third;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; second=nums[p];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return false;}该代码背后的全部思想是,如果我们发现一对值按升序排列,则只有在新对的第一个值小于旧对的第一个值时,才可以用新的对数递增序列替换该对。新对的第二个值小于旧对的第二个值。同时,我们检查数字是否大于将完成序列的第二个数字(true在这种情况下,我们将返回)。代码开始比较值从第三到第二,而不是第一到第二,但是思想与上面相同。

侃侃尔雅

这是一种可能的解决方案:public static boolean increasingTriplet(int[] nums) {&nbsp; &nbsp; for (int i = 0; i < nums.length-2; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; for (int j = i+1; j < nums.length-1; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (nums[j] > nums[i]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = j+1; k < nums.length; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (nums[k] > nums[j]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return false;}
随时随地看视频慕课网APP

相关分类

Java
我要回答