算法题:找出数组中比左边大比右边的小的元素

一道面试题

到想住科技(悦宿)面试的时候,面试官用的一道题。

题目

以时间复杂度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, 3, 2, 4, 5};
// int[] arr = new int[]{1, 1, 1, 1, 1};
// int[] arr = new int[]{};
// int[] arr = new int[]{5, 4, 3, 2, 1};
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. 该元素比放在它左边的所有元素都大;
  2. 该元素比放在它右边的所有元素都小。

第一次遍历先筛选出符合条件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();
}
}

需要和面试官问清楚的地方

面试官第一遍描述题目描述的没有特别细,还有一些问题需要确认:

  1. 要找的元素是大于和小于而不是大于等于和小于等于?
  2. 返回的元素的索引的顺序需要和输入顺序保持一致吗?
  3. 如果没有符合要求的元素,返回什么?

参考资料

  1. 2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素