#每日一面BAT#第21题 下标三元组


给定一个整数数组a, 希望判断下标三元组 i < j < k,满足a[i] < a[j] < a[k]。
是否可以用O(1)的空间,O(n)的时间找到一组?
已邀请:

cpcs - 诚实努力

赞同来自: caonima3000 天天


答案

解法1 O(n)时间 O(n)空间。
首先假设数组是a, 我们想找到这样3个index,比如3个index分别是i < j < k
我们看一下,当我们枚举j的时候,如果选取i和k? 一种可能是i选取a[0..j - 1]里面最小值的下标,而k选取a[j + 1..n - 1]最大值的下标。而这个东西我们可以用前缀、后缀的方法预处理出来。
比如我们可以算出b[i]表示 a[0..i]中最小值的下标,而c[i]表示a[i..n - 1]中最大值的下标。这个可以循环处理。
for (int i = 0; i < n; ++i) {
    b[i] = ((i == 0) || (a[b[i - 1]] > a[i]))? i : b[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
    c[i] = ((i == n - 1) || (a[c[i + 1]] < a[i]))? i : c[i + 1];
}


这样,选取的时候对i我们直接看一下b[i - 1]和c[i + 1]就可以了。
for (int i = 1; i + 1 < n; ++i) {
    if ((a[b[i - 1]] < a[i]) && (a[c[i + 1]] > a[i])) {
        return b[i - 1], i , c[i + 1]是一个解
    }
}


优化优化
解法2 O(n)时间,O(1)空间的算法。
利用LIS的思想,因为我们实际上就是要找到一个长度为3的单调子序列,那么我们可以用O(nlogn)的LIS思想,但是由于长度只维护到3,所以没有必要2分,而且没有必要用数组保存长度为x的单调子序列的最后一项的最小值,用变量存就好了,但思路是不变的。
我们这么记录x表示目前为止长度为1的单增子序列最后一项的最小值在数组a中的下标,实际上x就是我们刚才那个b数组,而y表示目前为止长度为2的单增子序列最后一项的最小值在数组a中的下标。根据单调子序列的性质,我们有a[x] < a[y], 这个其实就是那个O(nlogn)算法思想的核心。我们先让x = 0,让y = -1,表示目前长度为1的单增自序列就是第一项,没有长度为2的单增子序列。同时我们需要维护一个z,表示长度为2的单增自序列的首项,也就是y之前那一项。我们从i = 1开始维护x、y、z的值。
y = -1时a[y]定义为无穷大。 我们看一下a[i] 和a[x] a[y]的关系。 (注意始终有a[x] <a[y])
(1) 如果a[i] > a[y],则我们找到了三元组(z, y, i)满足条件
(2) 如果a[i] == a[y], 则这一项没有意义,无法扩展子序列
(3) 如果a[x] < a[i] < a[y] (当然我们可以把情况2也放到这里), 那么我们可以把长度为2的单调子序列最后一项更新一下,所以更新y = i, z = x,实际上a[x], a[i]是个长度为2的单增子序列,且最后一项比a[y]小。
(4) 如果a[i] == a[x], 则这一项没有意义, 无法扩展子序列
(5) 如果a[i] < a[x] (当然我们可以把情况4也放到这里), 那么我们可以把长度为1的单调子序列最后一项更新一下(也就是目前最小值),所以更新x = i
这个时间复杂度显然是O(n),空间复杂度是O(1)。
int x = 0;
int y = -1;
int z = -1;
for (int i = 1; i < n; ++i) {
    if ((y >= 0) && (a[i] > a[y])) {
        return 找到三元组(z, y, i)满足要求
    }
    else if (a[i] > a[x]) {
         y = i;
         z = x;
    }
    else {
        x = i;
    }
}

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~