求数组中等号最小指数差的算法
求数组中等号最小指数差的算法
提问于 2016-05-10 22:43:24
有没有人知道如何解决下一个问题：
例如，我们有一个数组，设为a= {1，0，-1，-2，-1，0，1，2，3，4，5，1}。
算法应该找到的是相同数字的指数之间最小差值的大小。在这个例子中，1的指数(数组a)的差值是6-0=0和11-6=5，零指数的差是5-1=4，负1的指数差是4-2=2，等等。算法应该返回2，因为我们可以看到它是相同数的指数的最小差。
有没有比O(n^2)更好的时间复杂度解决这个问题的方法？
回答 5
Stack Overflow用户
回答已采纳
发布于 2016-05-10 23:14:43
其他几个答案提出排序(元素，索引)对，可以在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;
}hash中的Insert/get是O(1)，因此给出了整个数组的O(n)。
Stack Overflow用户
发布于 2016-05-10 23:09:58
生成vector<pair<int, int>>，它将存储原始向量的值及其各自的索引。对于索引为i的每个值v，将(v，i)添加到向量中。
对向量进行排序(按值再按索引)。
然后遍历排序向量，找到相同值元素之间的最小(或最大，如果需要)距离。
这需要O(n log )步骤。
Stack Overflow用户
发布于 2016-05-10 23:36:24
首先，可以向序列(O(N))添加索引：
> L = [1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1].
[1,0,-1,-2,-1,0,1,2,3,4,5,1]
> LI = lists:zip(L, lists:seq(1, length(L))).
[{1,1},
{0,2},
{-1,3},
{-2,4},
{-1,5},
{0,6},
{1,7},
{2,8},
{3,9},
{4,10},
{5,11},
{1,12}]然后对其进行排序(O(N log N))：
> LS = lists:sort(LI).
[{-2,4},
{-1,3},
{-1,5},
{0,2},
{0,6},
{1,1},
{1,7},
{1,12},
{2,8},
{3,9},
{4,10},
{5,11}]然后找到所有相同值(O(N))的距离：
> LD = (fun F([{X, P1}|[{X,P2}|_]=T]) -> [{P2-P1, X, {P1, P2}} | F(T)]; F([_|T]) -> F(T); F([]) -> [] end)(LS).
[{2,-1,{3,5}},{4,0,{2,6}},{6,1,{1,7}},{5,1,{7,12}}]然后找到最小距离(O(N))：
> lists:min(LD).
{2,-1,{3,5}}它意味着值-1的最小距离-1在位置3和5之间，结果复杂度为O(N log N)。(示例代码在Erlang中。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37150139
复制相关文章
相似问题
腾讯云开发者
