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

coordinate35 發(fā)布于2019-08-15 14:03 / 2186人閱讀

摘要：如果右面能碰到一個數(shù)大于，說明必然存在一個遞增的三元組。復雜度空間時間測試代碼結(jié)果

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 .

實現(xiàn)代碼
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 .
     * 分析
         對一個無序數(shù)組，判讀遞增3數(shù)列是否存在
     * 直接解法
         掃描數(shù)組，遍歷三遍
     * 復雜度
         時間(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夾逼出結(jié)果
     * 復雜度
         時間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);

    }
    
}


結(jié)果
3 4 7 true
1 6 7 true
false

GPU云服務器云服務器最長遞增子序列最大子序列最長公共子序列動態(tài)規(guī)劃子序列代碼

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68480.html

LeetCode 334. Increasing Triplet Subsequence

摘要：描述給定一個未排序的數(shù)組，判斷這個數(shù)組中是否存在長度為的遞增子序列。說明要求算法的時間復雜度為，空間復雜度為。示例輸入輸出示例輸入輸出思路聲明三個變量，，用于表示首先遍歷數(shù)組，找到第一對滿足的數(shù)。此時依然有但是，不影響判斷的邏輯。 Description Given an unsorted array return whether an increasing subsequence o...

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

摘要：題目假設有一個無序的數(shù)組，如果數(shù)組中從左到右存在三個由小到大的數(shù)字，則返回。這個思路實在是非常的獨特，而且精煉這里它用兩個變量分別記錄了已經(jīng)遍歷過的數(shù)字中最小的數(shù)字和第二小的數(shù)字，一旦找到比這兩個數(shù)字都大的數(shù)字就證明一定存在一個升序。題目 Given an unsorted array return whether an increasing subsequence of lengt...

ASCH 2019-08-16 13:47 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點。或者拉到本文最下面，添加的微信等會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 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

摘要：本質(zhì)找出最長的遞增子序列的長度，可以是不連續(xù)的。應用判斷滿足一定條件的子序列的最大長度，用動態(tài)數(shù)組加以處理。二分法確定滿足條件的位置。類似二分法查找元素，查找某種情況的子序列。本質(zhì)：找出最長的遞增子序列的長度，可以是不連續(xù)的。用一個數(shù)組存儲遞增子序列，遍歷原始數(shù)組，每增加一個數(shù)，往里添加到對應的順序，記錄他的位置，即為此數(shù)組的長度。成立的理由：每一個數(shù)添加以后，都有對...

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

摘要：題目不要求連續(xù)的三個增長數(shù)，所以只需要更新其中較小的兩個數(shù)，并在第三個數(shù)滿足條件的情況下返回即可。 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