国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode334. Increasing Triplet Subsequence

ASCH / 1085人閱讀

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

題目 
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

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

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

思路一: 找到中間位置

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

    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)的時(shí)間復(fù)雜度，但是違背了O(1）的空間復(fù)雜度

思路二：找到最小的兩個(gè)數(shù)字

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

    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;
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • LeetCode 334. Increasing Triplet Subsequence

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

    saucxs 評論0 收藏0

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

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

  • [LeetCode] Increasing Triplet Subsequence

    摘要：題目不要求連續(xù)的三個(gè)增長數(shù)，所以只需要更新其中較小的兩個(gè)數(shù)，并在第三個(gè)數(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 評論0 收藏0

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會(huì)折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號(hào)上。三匯總返回目錄在月日月日這半個(gè)月中，做了匯總了數(shù)組知識(shí)點(diǎn)。或者拉到本文最下面，添加的微信等會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 評論0 收藏0

  • LeetCode[300] Longest Increasing Subsequence

    摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長的。保證升序相等也要替換這個(gè)值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

    blankyao 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<