资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/[Leetcode] Increasing Triplet Subsequence 递增的三元子序列

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

coordinate35 / 2258人阅读

摘要：如果右面能碰到一个数大于，说明必然存在一个递增的三元组。复杂度空间时间测试代码结果

</>复制代码 
  1. Given an unsorted array return whether an increasing subsequence of
    length 3 exists or not in the array. More specifically, if there exists i , j , k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 return true else return false . Your function 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 .

实现代码
IncreasingTripletSubsequence.java

</>复制代码 
  1. package array;
  2. import java.util.Arrays;
  3. import util.Print;
  4. public class IncreasingTripletSubsequence {
  5.     /**
  6.      * 描述
  7.         Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
  8.         More specifically, if there exists i , j , k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j
  9.         < k ≤ n-1 return true else return false .
  10.         Your function should run in O(n) time complexity and O(1) space complexity.
  11.         Examples:
  12.         Given [1, 2, 3, 4, 5] , return true .
  13.         Given [5, 4, 3, 2, 1] , return false .
  14.      * 分析
  15.          对一个无序数组，判读递增3数列是否存在
  16.      * 直接解法
  17.          扫描数组，遍历三遍
  18.      * 复杂度
  19.          时间(n^3),空间 (1)
  20.      * @param nums
  21.      * @return
  22.      */
  23.     public boolean Solution1(int[] nums){
  24.         
  25.         int min=nums[0];
  26.         
  27.         for(int i=0;i= nums[j])
  28.                     continue;
  29.                 for(int k=j+1;knums[j]){
  30.                         Print.Int(nums[i]);
  31.                         Print.Int(nums[j]);
  32.                         Print.Int(nums[k]);
  33.                         return true;    
  34.                     }
  35.                 }
  36.             }
  37.         
  38.         return false;        
  39.     }
  40.     
  41.     /**
  42.      * 夹逼解法
  43.          对每一个i用j,k夹逼出结果
  44.      * 复杂度
  45.          时间O(n^2),,空间(1)
  46.      * @param nums
  47.      * @return
  48.      */
  49.     public boolean Solution2(int[] nums){
  50.                 
  51.         for(int i=0;i=nums[j] && j=nums[k] && j
  52. 测试代码
    IncreasingTripletSubsequenceTest.java
  53. </>复制代码 
    1. package array;
    2. import org.junit.Assert;
    3. import org.junit.Before;
    4. import org.junit.Test;
    5. public class IncreasingTripletSubsequenceTest {
    6.     private IncreasingTripletSubsequence s;
    7.     
    8.     @Before
    9.         public void setUp() {
    10.          s = new IncreasingTripletSubsequence();
    11.         }
    12.      
    13.     @Test
    14.     public void testSolution1() {
    15.         
    16.         int[] nums = {3,4,1,7,5,2};
    17.         boolean expect = true;
    18.         
    19.         boolean result = s.Solution1(nums);
    20.         System.out.println(result);
    21.         Assert.assertEquals(expect, result);
    22.     }
    23.     @Test
    24.     public void testSolution2() {
    25.         
    26.         int[] nums ={9,1,6,8,7};
    27.         boolean expect = true;
    28.         
    29.         boolean result = s.Solution2(nums);
    30.         System.out.println(result);
    31.         Assert.assertEquals(expect, result);
    32.     }
    33.     @Test
    34.     public void testSolution3() {
    35.         
    36.         int[] nums ={5,4,3,2,1};
    37.         boolean expect = false;
    38.         
    39.         boolean result = s.Solution3(nums);
    40.         System.out.println(result);
    41.         Assert.assertEquals(expect, result);
    42.     }
    43.     
    44. }
  54. 结果
  55. </>复制代码 
    1. 3 4 7 true
    2. 1 6 7 true
    3. false
               
  56.                
  57.                                            
  58.                        
  59.
云服务器 GPU云服务器 最长递增子序列 最大子序列 最长公共子序列 动态规划 子序列 代码

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

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

相关文章

  • LeetCode 334. Increasing Triplet Subsequence

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

    saucxs 评论0 收藏0

  • leetcode334. Increasing Triplet Subsequence

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

    ASCH 评论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

    摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。 本质： 找出最长的递增子序列的长度，可以是不连续的。 用一个数组存储 递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。 成立的理由：每一个数添加以后，都有对...

    amc 评论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

发表评论

登陆后可评论

0条评论

coordinate35

男|高级讲师
我要私信

TA的文章

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