Facebook 2016 面试题1 | 递增三元组子序列

Facebook 2016 面试题1 | 递增三元组子序列

题目描述

给出一个无序的整数序列，返回是否存在递增的三元组子序列。

即返回true；如果不存在则返回false。 请给出一个O(N)时间复杂度以及O(1)额外空间的算法。Example 1：​​​[1, 2, 3, 4, 5]​​​ 返回true。Example 2:​​[5, 4, 3, 2, 1]​​ 返回false。

分析解答

读者不难想到穷举的方法，先穷举第一个数，再穷举找到第二个数（比第一个大），再穷举第三个数（比第二个数大），得到答案。但这样穷举过于低效，与要求的O(N)相距甚远。还有一种穷举方法是先预处理得到一个数组p，p[i]表示是否存在这样的j, j>i and arr[j]>arr[i]。这种方法符合时间复杂度的要求，但是额外空间是O(N)。因此我们需要换种思路，一边穷举一边记录已知的有用信息。当我们穷举到第i个数时，假设我们尚未找到答案，那么有以下几种情况：

我们只找到一个数（前i-1个数没有递增的两个数），此时我们记录前i-1个数的最小值。我们已找到递增的二元组子序列，此时我们需要记录的是这样的最小二元组（以第二个数为第一关键字）

可以发现，有时我们需要记录第三个数。比如已有递增子序列（3，5），之后又出现一个数1，我们必须记录1，因为如果之后出现2，（1，2）当递增序列会覆盖（3，5）。

参考代码1：O(n) memory：

public class Solution{ public boolean increasing Triplet(int []nums){ if(nums.lendth<2) return false; int n =nums.lendth; boolean[]has_first_small =new booleam[n]; int smallest =num[0]; has_first_small[0]=false; for(int i=0;i=0;i--){ if(has_first_small[i]==true){ if(num[i]

参考代码2：O(1) memory

public class Solution{ public: bool increasingTriplet(vector&nums){ int first =INT_MAX,second =INT_MAX; for(int now:nums){ if(now<=first){ first =now; continue; } if(firstsecond){ return true; } } return false; }};

面试官角度分析

此题的难点在于时空复杂度的限制，考验面试者提取关键信息的能力。笔者认为给出一个可行算法，比如如果能够做到O(n)时间复杂度复杂度，O(n)空间复杂度就可以达到hire ，如果能够优化空间复杂度达到O(1)那么就可以达到达到strong hire。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。