字节跳动-国际化电商三面算法题：求满足特定条件的元素索引

字节跳动-国际化电商三面算法题：求满足特定条件的元素索引

前言

大家好，我是程序员吴哥。

这两天有同学给我发来信息。

他提到了字节跳动国际电商第三次面试时遇到的一道算法题。

我搜索过这个问题，但没找到。

因此，我赶紧把这个原始问题分享给大家。

标题描述

找出数组中大于左侧元素且小于右侧元素的元素，并返回这些元素的索引

所需时间复杂度

输入：[2, 3, 1, 8, 9, 20, 12]

输出：3、4

解释：数组中的 8 和 9 符合题目要求，它们的索引分别是 3 和 4。

问题分析

最简单的想法就是遍历数组，正向和反向遍历每个元素，看是否满足条件。

伪代码如下

for(int i = 0; i < n; i ++) {
  for(int j = 0; j < i; j ++) {
    //左侧是否都比它小
  }
  for(int k = j + 1; k < n; k ++) {
    //右侧是否都比它大
  }
  //若两条件均满足则记录下来
}

这个解法不符合题目要求。

正如题目要求，外循环无法优化，有什么办法可以优化内循环吗？

一些！

通过分析可以得出，对于每个元素，如果它大于左边的最大值，并且小于右边的最小值，则满足条件。

如果有两个这样的数组，

[i] 表示原数组 [0, i) 中的最大值

[i] 表示原数组(i,n)的最小值

内层循环可以通过[i] < nums[i] && nums[i] < [i] 来判断。

对于和两个数组，预先计算出来，即可得到各个数组。

递归如下：

总时间复杂度为

这个问题其实不难，但如果你在面试时第一次看到它并思考它，你很可能会非常紧张。

下面是 C++ 的参考实现和

参考代码 C++

#include 
#include 
#include 
using namespace std;

vector<int> find(vector<int> nums) {
    vector<int> res;
    int n = nums.size();
    vector<int> left_max(n, INT_MIN);
    vector<int> right_min(n, INT_MAX);
    for (int i = 1; i < n; i++) {
        left_max[i] = max(left_max[i - 1], nums[i - 1]);
    }
    for (int i = n - 2; i >= 0; i--) {
        right_min[i] = min(right_min[i + 1], nums[i + 1]);
    }
    for (int i = 0; i < n; i++) {
        if (left_max[i] < nums[i] && nums[i] < right_min[i]) {
            res.push_back(i);
        }
    }
    return res;
}
int main()
{
    vector<int> arr = {2,3,1,8,9,20,12};
    auto res = find(arr);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << ' ';
    }
}

def find(nums):
    n = len(nums)
    res = []
    left_max = [float("-inf") for i in range(n)] # [0, i) 最大的值
    right_min = [float("inf") for i in range(n)] # (i, n) 最小的值
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], nums[i-1])
    for i in range(n-2,-1,-1):
        right_min[i] = min(right_min[i+1], nums[i+1])
    for i in range(n):
        if left_max[i] < nums[i] < right_min[i]:
            res.append(i)
    return res
print(find([2,3,1,8,9,20,12]))