一道面试题
到想住科技(悦宿)面试的时候,面试官用的一道题。
题目
以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素:
(1)该元素比放在它左边的所有元素都大;
(2)该元素比放在它右边的所有元素都小。
输入:一个数组
输出:返回一个数组,数组中保存的是符合条件的元素的下标。
解答1[Java]:
核心思路
一个数要比它左边的所有数要大,比右边的所有数要小,那么它必定大于左边元素的最大值,同时小于右边元素的最小值。
两次遍历。第一次遍历从后向前,找出第 i 个元素右边元素的最小值,保存在 rightMin 数组中。第二次遍历,从前向后,使用一个临时变量保存左边元素的最大值。一边判断一边更新。
代码
1 | import java.util.ArrayList; |
最后返回值的时候使用了 Java SE 8 中的流库。如果不使用这种方式,可以自己创建一个数组,然后遍历 list 把每一个元素存到数组中。
测试
加上 main 函数测试即可。
1 | public static void main(String[] args) { |
解答2[Java]:
核心思路
解答1中的思路是第一次遍历的时候把右边的最小值存下来。其实可以不保存,直接正反遍历两次选出符合要求的元素即可。
题目的要求可以看作两个条件:
- 该元素比放在它左边的所有元素都大;
- 该元素比放在它右边的所有元素都小。
第一次遍历先筛选出符合条件1的元素。正向遍历,判断一个元素是否大于其左边所有元素的最大值,把满足条件的保存在 list 中。
第二次遍历,就找出不满足条件2,但是满足条件1的,把这个元素从 list 中移出去。
两次遍历之后,list 中剩下的就是既符合条件1,又符合条件2的元素了。
代码
1 | import java.util.ArrayList; |
需要和面试官问清楚的地方
面试官第一遍描述题目描述的没有特别细,还有一些问题需要确认:
- 要找的元素是大于和小于而不是大于等于和小于等于?
- 返回的元素的索引的顺序需要和输入顺序保持一致吗?
- 如果没有符合要求的元素,返回什么?