查找数组中相等数字的最小索引差的算法

Question

有没有人知道如何解决下一个问题:

我们有一个数组，例如让它成为 a = {1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1}。

算法应该找到的是相同数字的索引之间的最小差异的大小。 在此示例(数组 a)中，1 的索引差异为 6-0=0 和 11-6=5，0 的索引差异为 5-1=4，负 1 的索引的差异为 4-2= 2 等等。 该算法应该返回 2，因为我们可以看到它是相同数字的索引的最小差异。

有没有比 O(n^2) 更好的时间复杂度来解决这个问题的方法？

Answer 1

其他几个答案提出可以在 O(n*logn) 中完成的排序(元素、索引)对。但是，可以在 O(n) 时间内做得更好。不需要对数组进行排序，也不需要保留所有的(元素，索引)对，因为可以贪婪地找到最小值。

遍历数组一次并将每个元素的最后一个索引存储在散列中。

int smallestDifference(int[] a) {
    Map<Integer, Integer> lastIndex = new HashMap<>();
    int minDiff = Integer.MAX_VALUE;
    for (int i = 0; i < a.length; i++) {
        if (lastIndex.contains(a[i])) {
            minDiff = Math.min(minDiff, i - lastIndex.get(a[i]));
        }
        lastIndex.put(a[i], i);
    }
    return minDiff;
}

从散列中插入/获取的时间复杂度为 O(1)，因此整个数组的复杂度为 O(n)。