LeetCode 334. Increasing Triplet Subsequence

saucxs 發布于2019-07-31 10:14 / 2837人閱讀

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

Description

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

描述

給定一個未排序的數組，判斷這個數組中是否存在長度為 3 的遞增子序列。

數學表達式如下:

如果存在這樣的 i, j, k, 且滿足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否則返回 false 。
說明: 要求算法的時間復雜度為 O(n)，空間復雜度為 O(1) 。

示例 1:

輸入: [1,2,3,4,5]
輸出: true
示例 2:

輸入: [5,4,3,2,1]
輸出: false

思路

聲明三個變量 i，j，k 用于表示 nums[i] < nums[j] < nums[k]

首先遍歷數組，找到第一對滿足 nums[i] < nums[j] 的數。

然后，另 k = j + 1，這個時候我們考慮以下情況

如果 nums[k] 大于 nums[j] 說明已經有三個數滿足條件，我們返回 True；

如果 nums[k] 在 nums[i] 和 nums[j] 中間，那么只要后面有一個數大于 nums[j], 就一定會大于 nums[k],于是我們更新 j = k；

如果 nums[k] 小于 nums[i]，說明我們找到了更小的數，更新 i = k。此時依然有 nums[i]

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-03-28 10:02:55
# @Last Modified by:   何睿
# @Last Modified time: 2019-03-28 11:08:49


class Solution:
    def increasingTriplet(self, nums: [int]) -> bool:
        # 聲明三個索引變量，用于記錄滿足條件的之
        i, j, k = 0, 1, 1
        # 元素的個數
        count = len(nums)
        # 找到數組中最前面遞增的兩個數
        while i < count and j < count and nums[i] >= nums[j]:
            i += 1
            j += 1
        # k 更新為 j 后面的那一個數
        k = j + 1
        while k < count:
            # 如果 nums[k] 比 nums[j] 大，說明已經有三個數滿足條件
            if nums[k] > nums[j]: return True
            # 如果 nums[k] 在 nums[i] 和 nums[j] 中間，我們丟掉 nums[j]
            # 更新現有的 j 為 k，因為如果接下來有個數比 nums[j]大，那么一定比 nums[k] 大
            if nums[i] < nums[k] <= nums[j]: j = k
            # 如果 nums[k] 比 nums[i] 還小，我們更新 i 
            if nums[k] <= nums[i]: i = k
            k += 1
        # 前面沒有滿足條件的數，返回 False
        return False

源代碼文件在這里。
?本文首發于何睿的博客，歡迎轉載，轉載需保留文章來源，作者信息和本聲明.

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43482.html

leetcode334. Increasing Triplet Subsequence

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

ASCH 2019-08-16 13:47 評論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