3

面试时被问到以下问题（遗憾的是我找不到比 N^2 更好的答案）

arr对于大小为 N的给定数组unsigned int，对于每个元素（在索引中i）我应该返回索引中的一个元素j（j > i），arr[j] > arr[i] 即我应该返回数组 res 其中 res[i] 有一个 arr[j ],j>i,arr[j] > arr[i],j 是所有索引 k 中的最小值，例如 arr[k] > arr[i]

arr[] = {3,1,4,2,5,7};
res[] = {2,2,4,4,5,-1};//-1 says no such index

有什么建议可以以更好的时间复杂度来做吗？谢谢

4

3 回答 3

6

O(N) 时间和 O(N) 空间复杂度：

创建空栈，从右边迭代数组

对于每个迭代的项目：只要顶部的项目小于当前项目，就不断从堆栈中弹出，然后如果堆栈变空，则右侧没有更大的元素，如果不是，那是当前元素右侧的第一个更大的项目，将当前项压入堆栈

void GetFirstRight(int* arr, int size, int* res){
  stack<int> s;
  for (int i = size - 1; i >= 0; --i) {
    while (!s.empty() && s.top() <= arr[i]) s.pop();
    if (s.empty()) { 
      res[i] = -1;
    } else {
      res[i] = s.top();
    }
    s.push(arr[i]);
  }
}
于 2013-11-06T07:42:18.560 回答
3

O(n) 算法：

维护一堆仍未解决的索引。这将被排序，以便最小的未解决值位于顶部。当你到达一个新元素时，从堆栈中弹出，直到新元素的值小于堆栈顶部的值。对于您弹出的每个，答案是当前索引。然后推送当前索引。最后，仍然在堆栈上的任何结果都是 -1。

代码（C++）：

stack<int> unsolved;
int arr[] = {3,1,4,2,5,7}, N = 6;
int res[1234];

int main() {
    for (int i = 0; i < N; i++) {
        while (!unsolved.empty() && arr[unsolved.top()] < arr[i]) {
            res[unsolved.top()] = i;
            unsolved.pop();
        }
        unsolved.push(i);
    }
    while (!unsolved.empty()) {
        res[unsolved.top()] = -1;
        unsolved.pop();
    }
    // Print results
    for (int i = 0; i < N; i++) printf("%d%c", res[i], i==N-1 ? '\n' : ' ');

    return 0;
}

输出：

2 2 4 4 5 -1
于 2013-11-06T07:46:09.713 回答
0

保持一个并行数组b。使b[0]=0。运行以遍历a的元素。随着您的进行，将b的值设置为 a的连续单元格的差异。

因此，如果

a[0]=9
a[1]=4
a[2]=17
a[3]=2
a[4]=3
a[5]=6
a[6]=0
a[7]=3
a[8]=1
a[9]=1
a[10]=7

然后，

b[0]=0
b[1]=-5
b[2]=13
b[3]=-15
b[4]=1
b[5]=3
b[6]=-6
b[7]=3
b[8]=-2
b[9]=0
b[10]=6

您应该关心的是b数组中的 (-) 单元格。现在，开始在数组b上向后迭代——从 上面的b[10]开始，例如。保持一个currentMax值。最初设置为数组上的第一个最大值 (+) - 对于数组末尾的 (-) 条目，您无能为力。当您从b[b.length]向下迭代到b[0]时，请执行以下操作：

更新currentMax：

currentMax += <value at the current cell of **b**>

if (currentMax<0) then /* you've hit elements-with-no-indexes*/ 然后继续直到你找到一个正的b[i]条目，当你找到一个时，将currentMax的值设置为它。

currentMax的 (+) 值表示重置currentMax的单元格是迄今为止访问过的所有单元格的索引的单元格，(-) 值是无索引单元格。

在上面，例如，a[10]处的 7 是a[3]..a[9]中所有的索引，因为 - currentMax是在单元格 10 处初始化的那个（之后不会重置） - currentMax之后的值所有这些添加仍然是 (+) 一直到单元格 4（单元格 4 反映了从单元格 3 到单元格 4 的变化）

在b[3]处，currentMax低于 0——意味着单元格 2 没有索引。在b[2]处找到的值为正，而currentMax 处为负——因此在 b[3]处设置 currentMax=13并继续迭代。

数组大小呈线性 - 需要O(n)时间。

于 2013-11-06T06:52:32.050 回答