资讯专栏INFORMATION COLUMN

LeetCode 334. Increasing Triplet Subsequence

saucxs / 2771人阅读

摘要:描述给定一个未排序的数组,判断这个数组中是否存在长度为的递增子序列。说明要求算法的时间复杂度为,空间复杂度为。示例输入输出示例输入输出思路声明三个变量,,用于表示首先遍历数组,找到第一对满足的数。此时依然有但是,不影响判断的逻辑。

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

源代码文件在 这里 。
©本文首发于 何睿的博客 ,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/43482.html

相关文章

  • leetcode334. Increasing Triplet Subsequence

    摘要:题目假设有一个无序的数组,如果数组中从左到右存在三个由小到大的数字,则返回。这个思路实在是非常的独特,而且精炼这里它用两个变量分别记录了已经遍历过的数字中最小的数字和第二小的数字,一旦找到比这两个数字都大的数字就证明一定存在一个升序。 题目 Given an unsorted array return whether an increasing subsequence of lengt...

    ASCH 评论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 评论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 评论0 收藏0
  • LeetCode 攻略 - 2019 年 8 月上半月汇总(109 题攻略)

    摘要:每天会折腾一道及以上题目,并将其解题思路记录成文章,发布到和微信公众号上。三汇总返回目录在月日月日这半个月中,做了汇总了数组知识点。或者拉到本文最下面,添加的微信等会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 评论0 收藏0
  • LeetCode[300] Longest Increasing Subsequence

    摘要:再用二分法找当前值应该在排好序的数组中的插入位置。因为要找的是最长的序列,所以每次将排好序的数组中替换成已经排好序的,会能保证得到的结果是最长的。保证升序相等也要替换这个值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

    blankyao 评论0 收藏0

发表评论

0条评论

saucxs

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<