資訊專欄INFORMATION COLUMN
摘要：描述給定一個(gè)未排序的數(shù)組，判斷這個(gè)數(shù)組中是否存在長(zhǎng)度為的遞增子序列。說(shuō)明要求算法的時(shí)間復(fù)雜度為，空間復(fù)雜度為。示例輸入輸出示例輸入輸出思路聲明三個(gè)變量，，用于表示首先遍歷數(shù)組，找到第一對(duì)滿足的數(shù)。此時(shí)依然有但是，不影響判斷的邏輯。
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
給定一個(gè)未排序的數(shù)組，判斷這個(gè)數(shù)組中是否存在長(zhǎng)度為 3 的遞增子序列。
數(shù)學(xué)表達(dá)式如下:
如果存在這樣的 i, j, k, 且滿足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否則返回 false 。
說(shuō)明: 要求算法的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1) 。
示例 1:
輸入: [1,2,3,4,5]
輸出: true
示例 2:
輸入: [5,4,3,2,1]
輸出: false
聲明三個(gè)變量 i，j，k 用于表示 nums[i] < nums[j] < nums[k]
首先遍歷數(shù)組，找到第一對(duì)滿足 nums[i] < nums[j] 的數(shù)。
然后，另 k = j + 1，這個(gè)時(shí)候我們考慮以下情況
如果 nums[k] 大于 nums[j] 說(shuō)明已經(jīng)有三個(gè)數(shù)滿足條件，我們返回 True；
如果 nums[k] 在 nums[i] 和 nums[j] 中間，那么只要后面有一個(gè)數(shù)大于 nums[j], 就一定會(huì)大于 nums[k],于是我們更新 j = k；
如果 nums[k] 小于 nums[i]，說(shuō)明我們找到了更小的數(shù)，更新 i = k。此時(shí)依然有 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:
# 聲明三個(gè)索引變量，用于記錄滿足條件的之
i, j, k = 0, 1, 1
# 元素的個(gè)數(shù)
count = len(nums)
# 找到數(shù)組中最前面遞增的兩個(gè)數(shù)
while i < count and j < count and nums[i] >= nums[j]:
i += 1
j += 1
# k 更新為 j 后面的那一個(gè)數(shù)
k = j + 1
while k < count:
# 如果 nums[k] 比 nums[j] 大，說(shuō)明已經(jīng)有三個(gè)數(shù)滿足條件
if nums[k] > nums[j]: return True
# 如果 nums[k] 在 nums[i] 和 nums[j] 中間，我們丟掉 nums[j]
# 更新現(xiàn)有的 j 為 k，因?yàn)槿绻酉聛?lái)有個(gè)數(shù)比 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
# 前面沒(méi)有滿足條件的數(shù)，返回 False
return False
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來(lái)源 ，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43482.html
摘要：題目假設(shè)有一個(gè)無(wú)序的數(shù)組，如果數(shù)組中從左到右存在三個(gè)由小到大的數(shù)字，則返回。這個(gè)思路實(shí)在是非常的獨(dú)特，而且精煉這里它用兩個(gè)變量分別記錄了已經(jīng)遍歷過(guò)的數(shù)字中最小的數(shù)字和第二小的數(shù)字，一旦找到比這兩個(gè)數(shù)字都大的數(shù)字就證明一定存在一個(gè)升序。 題目 Given an unsorted array return whether an increasing subsequence of lengt...
摘要：如果右面能碰到一個(gè)數(shù)大于，說(shuō)明必然存在一個(gè)遞增的三元組。復(fù)雜度空間時(shí)間測(cè)試代碼結(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...
摘要：題目不要求連續(xù)的三個(gè)增長(zhǎng)數(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...
摘要：每天會(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...
摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L(zhǎng)的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長(zhǎng)的。保證升序相等也要替換這個(gè)值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...
閱讀 2435·2021-09-01 10:41
閱讀 1451·2019-08-30 14:12
閱讀 520·2019-08-29 12:32
閱讀 2868·2019-08-29 12:25
閱讀 2943·2019-08-28 18:30
閱讀 1713·2019-08-26 11:47
閱讀 989·2019-08-26 10:35
閱讀 2597·2019-08-23 18:06
