一道面试题
到想住科技（悦宿）面试的时候，面试官用的一道题。
题目
以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素：
（1）该元素比放在它左边的所有元素都大；
（2）该元素比放在它右边的所有元素都小。
输入：一个数组
输出：返回一个数组，数组中保存的是符合条件的元素的下标。
解答1[Java]：
核心思路
一个数要比它左边的所有数要大，比右边的所有数要小，那么它必定大于左边元素的最大值，同时小于右边元素的最小值。
两次遍历。第一次遍历从后向前，找出第 i 个元素右边元素的最小值，保存在 rightMin 数组中。第二次遍历，从前向后，使用一个临时变量保存左边元素的最大值。一边判断一边更新。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.ArrayList;
import java.util.List;
public class Main {
public int[] findElements(int[] nums) {
List<Integer> list = new ArrayList<>();
int[] rightMin = new int[nums.length];
int min = Integer.MAX_VALUE;
for (int i = nums.length - 1; i >= 0; --i) {
rightMin[i] = min;
if (nums[i] < min) {
min = nums[i];
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > max) {
max = nums[i];
if(nums[i] < rightMin[i]) {
list.add(i);
}
}
}
return list.stream().parallel().mapToInt(Integer::intValue).toArray();
}
}
|
最后返回值的时候使用了 Java SE 8 中的流库。如果不使用这种方式，可以自己创建一个数组，然后遍历 list 把每一个元素存到数组中。
测试
加上 main 函数测试即可。
1
2
3
4
5
6
7
8
9
10
11
12
| public static void main(String[] args) {
int[] arr = new int[]{1, 1, 2, 3, 4};
Main invoker = new Main();
int[] result = invoker.findElements(arr);
for (int a : result) {
System.out.printf("%d ", a);
}
}
|
解答2[Java]：
核心思路
解答1中的思路是第一次遍历的时候把右边的最小值存下来。其实可以不保存，直接正反遍历两次选出符合要求的元素即可。
题目的要求可以看作两个条件：
- 该元素比放在它左边的所有元素都大；
- 该元素比放在它右边的所有元素都小。
第一次遍历先筛选出符合条件1的元素。正向遍历，判断一个元素是否大于其左边所有元素的最大值，把满足条件的保存在 list 中。
第二次遍历，就找出不满足条件2，但是满足条件1的，把这个元素从 list 中移出去。
两次遍历之后，list 中剩下的就是既符合条件1，又符合条件2的元素了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.ArrayList;
import java.util.List;
public class Main {
public int[] findElements(int[] nums) {
List<Integer> list = new ArrayList<>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > max) {
max = nums[i];
list.add(i);
}
}
int min = Integer.MAX_VALUE;
for (int i = nums.length - 1; i >= 0; --i) {
if (nums[i] >= min && list.contains(i)) {
list.remove(i);
} else {
min = nums[i];
}
}
return list.stream().parallel().mapToInt(Integer::intValue).toArray();
}
}
|
需要和面试官问清楚的地方
面试官第一遍描述题目描述的没有特别细，还有一些问题需要确认：
- 要找的元素是大于和小于而不是大于等于和小于等于？
- 返回的元素的索引的顺序需要和输入顺序保持一致吗？
- 如果没有符合要求的元素，返回什么？
参考资料
- 2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素