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

coordinate35 發布于2019-08-15 14:03 / 2193人閱讀

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

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

云服務器 GPU云服務器最長遞增子序列最大子序列最長公共子序列動態規劃子序列代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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