leetcode334. Increasing Triplet Subsequence

ASCH 發布于2019-08-16 13:47 / 1082人閱讀

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

題目

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

假設有一個無序的數組，如果數組中從左到右存在三個由小到大的數字，則返回true。否則返回false。

題目的額外要求是：O(n)的時間復雜度和O(1)的空間復雜度

思路一: 找到中間位置

其實我們知道只要找到這樣一個數字，該數字左邊存在比它小的數字，右邊存在比它大的數字，就可以確信該數字一定屬于某個上升序列的中間數字。所我們可以先從左往右得出每一個數字左邊是否有比它小的數字，再從有望走得出右邊是否有比它大的數字，最后再根據這兩個信息判斷該數字是否為上升序列的中間數字。

    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        
        boolean[] hasLeftMin = new boolean[nums.length];
        boolean[] hasRightMax = new boolean[nums.length];
        
        int left = 0;
        int right = nums.length - 1;
        for(int i = 1 ; i nums[left]) {
                hasLeftMin[i] = true;
            } else {
                left = i;
            }
            if(nums[nums.length - i - 1] < nums[right]) {
                hasRightMax[nums.length - i - 1] = true;
            } else {
                right = nums.length - i - 1;
            }
        }
        
        for(int i = 1 ; i < nums.length - 1 ; i++) {
            if(hasLeftMin[i] && hasRightMax[i]) return true;
        }
        return false;
    }

這種思路雖然遵循了O(N)的時間復雜度，但是違背了O(1）的空間復雜度

思路二：找到最小的兩個數字

思路二是從討論區排名第一的回答中挖過來的。這個思路實在是非常的獨特，而且精煉！這里它用兩個變量分別記錄了已經遍歷過的數字中最小的數字和第二小的數字，一旦找到比這兩個數字都大的數字就證明一定存在一個升序。

    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
        for(int n : nums) {
            if(n <= small) {
                small = n;
            } else if (n<=big) {
                big = n;
            } else {
                return true;
            }
        }
        return false;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Triplet Increasing Subsequence Leetcod

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72332.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
[Leetcode] Increasing Triplet Subsequence 遞增的三元子序列

摘要：如果右面能碰到一個數大于，說明必然存在一個遞增的三元組。復雜度空間時間測試代碼結果 Given an unsorted array return whether an increasing subsequence oflength 3 exists or not in the array. More specifically, if there exists i , j , k suc...

coordinate35 2019-08-15 14:03 評論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
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

摘要：再用二分法找當前值應該在排好序的數組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數組中替換成已經排好序的，會能保證得到的結果是最長的。保證升序相等也要替換這個值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 評論0 收藏0