The O(N) Increasing Triplet Subsequence Algorithm

  • 时间:2020-09-24 11:41:27
  • 分类:网络文摘
  • 阅读:84 次

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

Checking Increasing Triplet Subsequence in O(N) Algorithm

The most intutive solution will be to bruteforce a triplet in O(N^3) and see if it is in increasing order. Obviously, this is inefficient. A Better solution is to record the smaller numbers as iterating the array.

This greedy approach works, as we are iterating the array from left to the right. If we find out a number that is different than the two numbers we have found – and both numbers are smaller than the current number, we know it has a increasing triplet subsequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;
        for (const auto &n: nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else return true;
        }
        return false; // can't find such triplet increasing subsequence
    }
};
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;
        for (const auto &n: nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else return true;
        }
        return false; // can't find such triplet increasing subsequence
    }
};

I have to say, this trick is elegant and makes the algorithm efficient in O(N) time and O(1) constant space.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
营养健康食品:向日葵的种子葵花籽  酿造酒之黄酒和白酒的营养价值  葡萄酒及啤酒的营养保健价值  保健食品广告九成以上虚假违法  生吃鸡蛋易引起沙门氏菌食物中毒  由副溶血弧菌污染引起的食物中毒  肉毒中毒是一种极为严重的食物中毒  绿色食品与有机食品的联系和区别  盘点人体需要的11种膳食营养补充剂  食品安全事件:商家无良心消费不放心 
评论列表
添加评论