- 浏览: 173232 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
在一个未排序的数组中查看是否存在三个元素,满足arr[i] < arr[j] < arr[k], (0 ≤ i < j < k ≤ n-1).
要求在线性时间找到,要求空间复杂度为O(1)。我们维护两个变量min1,min2, 使min1 <min2,并且min1在min2的左边,所以我们只要找到一个元素大于min2就可以返回true。这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
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.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
在一个未排序的数组中查看是否存在三个元素,满足arr[i] < arr[j] < arr[k], (0 ≤ i < j < k ≤ n-1).
要求在线性时间找到,要求空间复杂度为O(1)。我们维护两个变量min1,min2, 使min1 <min2,并且min1在min2的左边,所以我们只要找到一个元素大于min2就可以返回true。这样时间复杂度为O(n),空间复杂度为O(1)。代码如下:
public class Solution { public boolean increasingTriplet(int[] nums) { if(nums == null || nums.length < 3) return false; int min1 = Integer.MAX_VALUE; int min2 = Integer.MAX_VALUE; for(int i : nums) { if(i <= min1) min1 = i; else if(i <= min2) min2 = i; else if(i > min2) return true; } return false; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
LMS Longest Monotonically Increasing Sequence Algorithm
P8 INCREASING ENDOTHELIAL INSULIN-LIKE GROWTH FACTOR-1 RECEPTOR EXPRESSION REDUCES CIRCULATING LEUKOCYTES AND PROTECTS AGAINST ATHEROSCLEROSIS
[Translated]Increasing the Value of Simulation.pdf
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
Managing and Ever Increasing Number of Linux—PCs at DESY.pdf
aps004_increasing_range_of_dw1000_using_lna_v1.4.pdf
Increasing Interpretation of Web Topic Detection via Prototype Learning From Sparse Poisson Deconvolution
Challenge: 100Gbit/s around the corner1/37Network stack challengesat increasing speeds The 100Gbit/s challengeJesper Dangaard Brouer Red Hat inc.Linux Conf Au, New Zealand, January 2015Challenge: 100...
竞争环境下易逝品升价时点问题,张文思,李金林,随着收益管理的发展,动态定价在提升企业收入方面起了越来越重要的作用。本文通过建立博弈模型,讨论分析了双寡头竞争条件下易逝
这是一篇英文论文,主要介绍了xml在教育领域的应用。
生产率提高2.0
主要介绍了mysql Sort aborted: Out of sort memory, consider increasing server sort buffer size的解决方法,需要的朋友可以参考下
这是一个matlab环境下关于图强增强的源代码,内附测试图像和测试程序
leetcode卡950.-Reveal-Cards-In-Increasing-Order-medium-leetcode 在一副牌中,每张牌都有一个唯一的整数。 您可以按您想要的任何顺序订购甲板。 最初,所有牌面朝下(未显示)在一副牌中。 现在,您重复执行以下...
轻巧的React迷你图 :sparkles: :chart_increasing: 安装 yarn add @rowno/sparkline # or npm install --save @rowno/sparkline 例子 function Spark ( ) { const lines = [ { values : [ 789 , 880 , 676 ,...
关于单调增过程的集值随机积分,祁佳佳,张金平,在欧式空间$R^d$中,不同于在参考文献中用的可分解闭包的方法,这篇文章通过用有界可积选择的方法定义了关于单值非降过程${A_t(omega),tin
(CGRAs) have drawn increasing attention due to their flexibility and efficiency. Loops in applications are often mapped onto CGRAs for acceleration, and the mapping of loops onto CGRA is quite a ...
Increasing academic performance through contingent access to tutoring INCREASING ACADEMIC PERFORMANCE THROUGH CONTINGENT ACCESS TO TUTORING JEFFREY LEVENKRON, DAVID A. SANTOGROSSI AND DANIEL O’...
不具有增性算子的不动点及其对非线性积分方程的应用,赵增勤,林秀丽,利用锥理论,研究了不具有增性的算子 $A$ 不动点的存在性,该算子 $A$ 介于算子 $B_1$ 与 算子$B_2$ 之间, $B_1, B_2$ 具有某些增性....
提供语言支持和和 JSON规格图的交互式预览 :chart_increasing: 与其他在线dataViz devTools不同,您可以在断开连接的模式下使用它来制作地图原型 :world_map: 和图表 :chart_increasing: 随时随地 :airplane: ,在...