给定整数数组 A = [a0, a1, ..., an],找到 ai=aj 且 i ≠ j 的 ai 和 aj 之间的最小距离(或指示不存在这样的索引)。
因此我在C++中实现了一种朴素的O(n2)方法,通过迭代遍历数组查找相同的元素并适当地更新最小距离。
这个方法虽然可以正常工作,但是有人告诉我存在一种更“高效”的实现方式,使用 std::map,但是并没有明确说明哪种更高效。换句话说,您可以遍历输入数组,并在 map 中存储元素的第一次出现,对于每个后续出现,找到该出现与该元素在 map 中的第一个索引之间的距离。如果该距离小于当前最小值,则更新该最小值。
然而,我无法看出这种方式在何种方面更“高效”。就时间复杂度而言,您仍然需要遍历输入数组(O(n)),并使用 std::map::find 来确定一个元素是否为第一次出现(或不是),也是 O(n),总的时间复杂度为 O(n2)。就空间复杂度而言,除了数组/向量外,还要存储一个 map。请问我错过了什么?
编辑:我错误地认为 map::find 是 O(n) 的;插入和查找操作实际上是 O(log n),即使假设使用基本实现例如二分查找,也可以立即看出来。
因此我在C++中实现了一种朴素的O(n2)方法,通过迭代遍历数组查找相同的元素并适当地更新最小距离。
#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),即使假设使用基本实现例如二分查找,也可以立即看出来。