[Leetcode] Increasing Triplet Subsequence 递增的三元子序列

coordinate35 发布于2019-08-15 14:03 / 2072人阅读

摘要：如果右面能碰到一个数大于，说明必然存在一个递增的三元组。复杂度空间时间测试代码结果

Given an unsorted array return whether an increasing subsequence of
length 3 exists or not in the array. More specifically, if there exists i , j , k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 return true else return false . Your function should run in O(n) time complexity and O(1) space complexity. 
Examples: 
Given [1, 2, 3, 4, 5] , return true . 
Given [5, 4, 3, 2, 1] , return false .

实现代码
IncreasingTripletSubsequence.java

package array;

import java.util.Arrays;

import util.Print;

public class IncreasingTripletSubsequence {
    /**
     * 描述
        Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
        More specifically, if there exists i , j , k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j
        < k ≤ n-1 return true else return false .
        Your function should run in O(n) time complexity and O(1) space complexity.
        Examples:
        Given [1, 2, 3, 4, 5] , return true .
        Given [5, 4, 3, 2, 1] , return false .
     * 分析
         对一个无序数组，判读递增3数列是否存在
     * 直接解法
         扫描数组，遍历三遍
     * 复杂度
         时间(n^3),空间 (1)
     * @param nums
     * @return
     */
    public boolean Solution1(int[] nums){
        
        int min=nums[0];
        
        for(int i=0;i= nums[j])
                    continue;
                for(int k=j+1;knums[j]){
                        Print.Int(nums[i]);
                        Print.Int(nums[j]);
                        Print.Int(nums[k]);
                        return true;    
                    }
                }
            }
        
        return false;        
    }
    
    /**
     * 夹逼解法
         对每一个i用j,k夹逼出结果
     * 复杂度
         时间O(n^2),,空间(1)
     * @param nums
     * @return
     */
    public boolean Solution2(int[] nums){
                
        for(int i=0;i=nums[j] && j=nums[k] && j
测试代码
IncreasingTripletSubsequenceTest.java
package array;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class IncreasingTripletSubsequenceTest {

    private IncreasingTripletSubsequence s;
    
    @Before
        public void setUp() {
         s = new IncreasingTripletSubsequence();
        }
     
    @Test
    public void testSolution1() {
        
        int[] nums = {3,4,1,7,5,2};
        boolean expect = true;
        
        boolean result = s.Solution1(nums);
        System.out.println(result);
        Assert.assertEquals(expect, result);

    }

    @Test
    public void testSolution2() {
        
        int[] nums ={9,1,6,8,7};
        boolean expect = true;
        
        boolean result = s.Solution2(nums);
        System.out.println(result);
        Assert.assertEquals(expect, result);

    }
    @Test
    public void testSolution3() {
        
        int[] nums ={5,4,3,2,1};
        boolean expect = false;
        
        boolean result = s.Solution3(nums);
        System.out.println(result);
        Assert.assertEquals(expect, result);

    }
    
}


结果
3 4 7 true
1 6 7 true
false

私有云服务器托管最长递增子序列最大子序列最长公共子序列动态规划子序列代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68480.html

LeetCode 334. Increasing Triplet Subsequence

摘要：描述给定一个未排序的数组，判断这个数组中是否存在长度为的递增子序列。说明要求算法的时间复杂度为，空间复杂度为。示例输入输出示例输入输出思路声明三个变量，，用于表示首先遍历数组，找到第一对满足的数。此时依然有但是，不影响判断的逻辑。 Description Given an unsorted array return whether an increasing subsequence o...

saucxs 2019-07-31 10:14 评论0 收藏0
leetcode334. Increasing Triplet Subsequence

摘要：题目假设有一个无序的数组，如果数组中从左到右存在三个由小到大的数字，则返回。这个思路实在是非常的独特，而且精炼这里它用两个变量分别记录了已经遍历过的数字中最小的数字和第二小的数字，一旦找到比这两个数字都大的数字就证明一定存在一个升序。题目 Given an unsorted array return whether an increasing subsequence of lengt...

ASCH 2019-08-16 13:47 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0
leetcode-300-Longest Increasing Subsequence

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。本质：找出最长的递增子序列的长度，可以是不连续的。用一个数组存储递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。成立的理由：每一个数添加以后，都有对...

amc 2019-07-30 17:36 评论0 收藏0
[LeetCode] Increasing Triplet Subsequence

摘要：题目不要求连续的三个增长数，所以只需要更新其中较小的两个数，并在第三个数满足条件的情况下返回即可。 Problem Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should:Re...

cooxer 2019-08-14 14:03 评论0 收藏0