我试图想出一个快速算法,给定长度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]开始,您可以返回并包含所有元素,直到找到一个副本。
让我们用这个直觉来解决这个问题,从j0我们需要知道,在迭代的任何一点上,在找到一个副本之前,我们可以走多远也就是说,我们需要知道最少的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/

10-12 14:25
查看更多