我试图想出一个快速算法,给定长度n的任何数组,获得具有不同值的最大子数组。
例如,不同值的最大子数组
[1, 4, 3, 2, 4, 2, 8, 1, 9]
会是
[4, 2, 8, 1, 9]
这是我目前的解决方案,我认为它运行在o(n^2)中。这是因为check-dups在线性时间内运行,每次j或i递增时都会调用它。
arr = [0,...,n]
i = 0
j = 1
i_best = i
j_best = j
while i < n-1 and j < n:
if check_dups(arr, i j): //determines if there's duplicates in the subarray i,j in linear time
i += 1
else:
if j - i > j_best - i_best:
i_best = i
j_best = j
j += 1
return subarray(arr, i_best, j_best)
有人在线性时间内有更好的解吗?
请注意,这是伪代码,我不是在寻找一个答案,它依赖于特定语言的特定现有函数(如AR.Cub())。
谢谢!
最佳答案
考虑寻找以特定索引j
结尾的最大的不同值子数组的问题。从概念上讲,这是很简单的:从arr[j]
开始,您可以返回并包含所有元素,直到找到一个副本。
让我们用这个直觉来解决这个问题,从j
到0
我们需要知道,在迭代的任何一点上,在找到一个副本之前,我们可以走多远也就是说,我们需要知道最少的length(arr)
以便i
包含不同的值。(我假设subarray(arr, i, j)
将索引视为包含在内。)
如果我们在迭代的某个时刻(比如当subarray
时)知道i
,那么我们是否可以在j = k
时快速更新i
实际上,如果我们知道最后一次出现j = k+1
,那么我们就可以更新arr[k+1]
。我们可以用hashmap计算o(1)时间内的i := max(i, lastOccurrence(arr[k+1]) + 1)
。
伪码:
arr = ... (from input)
map = empty HashMap
i = 0
i_best = 0
j_best = 0
for j from 0 to length(arr) - 1 inclusive:
if map contains-key arr[j]:
i = max(i, map[arr[j]] + 1)
map[arr[j]] = j
if j - i > j_best - i_best:
i_best = i
j_best = j
return subarray(arr, i_best, j_best)
关于algorithm - 线性时间中不同值的最大子数组的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50039692/