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

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

摘要：如果右面能碰到一個(gè)數(shù)大于，說(shuō)明必然存在一個(gè)遞增的三元組。復(fù)雜度空間時(shí)間測(cè)試代碼結(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 .

實(shí)現(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 .
     * 分析
         對(duì)一個(gè)無(wú)序數(shù)組，判讀遞增3數(shù)列是否存在
     * 直接解法
         掃描數(shù)組，遍歷三遍
     * 復(fù)雜度
         時(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;        
    }
    
    /**
     * 夾逼解法
         對(duì)每一個(gè)i用j,k夾逼出結(jié)果
     * 復(fù)雜度
         時(shí)間O(n^2),,空間(1)
     * @param nums
     * @return
     */
    public boolean Solution2(int[] nums){
                
        for(int i=0;i=nums[j] && j=nums[k] && j
測(cè)試代碼
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