java - 在 O(n) 中查找数组中每个元素的下一次出现

Question

假设我有一个这样的数组:[ 1, 2, 3, 4, 5, 6, 1]

我想得到类似 1 ==> 6 的输出(对于元素 1(第 0 索引，在索引 6 处找到匹配项)

这意味着对于第 0 个 元素，下一个匹配项位于第 6 个索引处。

如果输入是 [4,6,4,6] 输出是 4 ==> 2 and 6 ==> 3

因为 4 的第一个匹配是在索引 2(即四)处找到的，而 6(第 2^nd 元素)的第一个匹配是在第 3^rd 索引处找到的

如果时间复杂度为 O(n²)，解决方案就非常简单。我试图使用堆栈在 O(n) 中使用此代码找到下一个最大的元素。但是我找不到对下一个相等元素执行相同操作的方法。

import java.util.Scanner;
import java.util.Stack;

public class NextGreatestElement {
    public static void main(String[] args) {
        int[] inp = {1,4,6,2,39};
        Stack<Integer> stack = new Stack<>();
        stack.push(inp[0]);
        for (int i = 1; i < inp.length; i++) {
            int element = inp[i];
            if (element > stack.peek()) {
                System.out.println(stack.peek() + " ==> " + element);
                stack.pop();
                while (!stack.isEmpty()) {
                    System.out.println(stack.pop() + " ==> " + element);
                }
                stack.push(element);
            } else if (element < stack.peek()) {
                stack.push(element);
            }
        }
        while (!stack.isEmpty()) System.out.println(stack.pop() + " ==> " + (-1));
    }
}

即使是算法也足够了。我不需要代码。

Answer 1

不可能用 O(n) 中的堆栈来实现它。您可以采用 HashMap 并从右到左迭代以保存最后一次出现的数字。它将为您提供 O(n) 平均时间复杂度:

int[] inp = {1, 2, 3, 1, 2, 1, 3};
Map<Integer, Integer> h = new HashMap<>();
List<Integer> result = new ArrayList<>();

for (int i = inp.length - 1; i >= 0; --i) {
    int cur = inp[i];
    int next = -1;
    if (h.containsKey(cur)) {
        next = h.get(cur);
    }   
    h.put(cur, i);
    result.add(next);
}

for (int i = 0; i < inp.length; ++i) {
    System.out.println("Number " + inp[i] + " next occurence at index " + result.get(inp.length - i - 1));
}

可运行版本:http://ideone.com/i6Cx09