在一个数组中查找任意一对相等元素之间的最小距离

Question

给定整数数组 A = [a₀, a₁, ..., a_n]，找到 a_i=a_j 且 i ≠ j 的 a_i 和 a_j 之间的最小距离（或指示不存在这样的索引）。

因此我在C++中实现了一种朴素的O(n²)方法，通过迭代遍历数组查找相同的元素并适当地更新最小距离。

#include <vector>
#include <climits>
#include <algorithm>

int MinPair(const std::vector<int>& nums)
{
    int ret = std::numeric_limits<int>::max();
    for(int i = 0; i != nums.size(); ++i)
    { 
        for(int j = 0; j != i; ++j)
        { 
            if(nums[i] == nums[j])  
                ret = std::min(ret, i - j);
        }
    }

    if(ret == std::numeric_limits<int>::max()) 
        return -1;

    return ret;
}

这个方法虽然可以正常工作，但是有人告诉我存在一种更“高效”的实现方式，使用 std::map，但是并没有明确说明哪种更高效。换句话说，您可以遍历输入数组，并在 map 中存储元素的第一次出现，对于每个后续出现，找到该出现与该元素在 map 中的第一个索引之间的距离。如果该距离小于当前最小值，则更新该最小值。

然而，我无法看出这种方式在何种方面更“高效”。就时间复杂度而言，您仍然需要遍历输入数组（O(n)），并使用 std::map::find 来确定一个元素是否为第一次出现（或不是），也是 O(n)，总的时间复杂度为 O(n2)。就空间复杂度而言，除了数组/向量外，还要存储一个 map。请问我错过了什么？

编辑：我错误地认为 map::find 是 O(n) 的；插入和查找操作实际上是 O(log n)，即使假设使用基本实现例如二分查找，也可以立即看出来。

- rw435

---

使用std :: map :: find来确定元素是否是第一次出现还是不是第一次出现也是O（n）吗？你确定吗？文档说：“复杂度：大小对数级别。” - arekolek

保持数组排序，您可以在O(n)时间内搜索重复项。 - FortyTwo

在搜索之前，您的容器是已排序还是未排序的？ - Francis Cugler

@arekolek 你是对的，确实是对数的！ - rw435

Answer 1

我最初发布了一个与grigor提到的解决方案类似的编码解决方案。 然后我意识到有一个明显的优化，使整个过程在最佳情况和平均情况下以O（N）时间运行。

typedef pair<bool, int> LastPositionFound;

int MinPair(const std::vector<int>& nums)
{
    unordered_map<int, LastPositionFound> table; // maps value found in array to the last position that value was seen at.
    int best_distance = -1;

    for (size_t index = 0; index < nums.size(); index++)
    {
        int value = nums[index];
        LastPositionFound& lpf = table[value];  // returns {false,0} if not found
        if (lpf.first)
        {
            int distance = index - lpf.second;
            if ((distance < best_distance) || (best_distance == -1))
            {
                best_distance = distance;
            }
        }

        // update reference to hash table entry
        lpf.first = true;
        lpf.second = index;
    }
    return best_distance;
}

- selbie

Answer 2

你可以将每个元素映射到其索引集合。因此，你会有类似于 map<int, set<int>> m 的东西，并遍历你的向量：for(int i = 0, i < nums.size(); ++i) m[nums[i]].insert(i)。之后，你可以遍历该映射，如果一个元素具有多个索引，则查找索引之间的最小距离。应该是 O(nlog(n))。

- grigor

---

保留所有值的意义何在？将重复元素的索引与先前出现的索引进行比较就足够了。为什么是 O(n log n)？无论是映射还是集合，插入的平均运行时间都为 O(1)。 - user4668606

@Paul（有序）集合和映射在C++中具有O(log n)的操作。C++还有无序映射，其预期复杂度为O(1)。 - Bernhard Barker

@Paul 这个问题标记为C++，答案提到了map和set，它们是C++标准API中有序容器类的名称，具有O(log n)复杂度的操作。 - Bernhard Barker