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) —
推荐阅读:6·1游园作文500字 战争,你伤害了这些羽翼还未丰满的孩童作文600字 家乡的梓山作文 阅读点亮我的心灵作文300字 春节逛花市作文 在苦难中行走 百度正式上线快速收录功能 如何让百度快速收录网页?快用百度站长平台“快速收录”功能! php和asp网站源码有什么不同?哪种代码语言更好? 装修公司网销业绩不好?原因和解决方法都在这里
- 评论列表
-
- 添加评论