时间戳

首页 > 解决方案 > 线性时间内不同值的最大子数组的算法

algorithm - 线性时间内不同值的最大子数组的算法

问题描述

我试图提出一个快速算法，给定任何长度为 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)

有没有人在线性时间内有更好的解决方案？

请注意，这是伪代码，我不是在寻找依赖于已定义语言的特定现有功能（例如 arr.contains()）的答案。谢谢！

标签： algorithmperformancetimedistinct-values

解决方案

考虑寻找以特定索引结尾j的最大不同值子数组的问题。从概念上讲，这很简单：从 开始arr[j]，您向后退并包含所有元素，直到找到重复项。

让我们用这种直觉来解决这个问题j。我们需要知道，在迭代的任何时候，在找到重复之前我们可以走多远。也就是说，我们需要知道最少包含不同值的内容。（我假设将索引视为包容性。）0length(arr)isubarray(arr, i, j)subarray

如果我们知道i迭代中的某个时间点（例如，何时j = k），我们能否快速更新i何时j = k+1？事实上，如果我们知道最后一次出现 是什么时候arr[k+1]，那么我们可以更新i := max(i, lastOccurrence(arr[k+1]) + 1). 我们可以lastOccurrence用 HashMap 在 O(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)

推荐阅读