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

Question

我正在尝试想出一个快速算法，给定任何长度为 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()）。谢谢！

Answer 1

将每个数字添加到哈希集中（如果它不在其中）。 Hashset的插入和查找都是O(1)。所以最终结果将是 O(n).

Answer 2

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

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

如果我们在迭代中的某个时刻知道 i（比如 j = k 时），我们能否在 j = k+1 时快速更新 i？事实上，如果我们知道 arr[k+1] 最后一次出现的时间是什么时候，那么我们就可以更新 i := max(i, lastOccurrence(arr[k+1]) + 1)。我们可以使用 HashMap 在 O(1) 时间内计算 lastOccurrence。

伪代码：

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)

Answer 3

如果您的数据允许 O(n) 稳定排序，我们可以调整 pkpnd 的算法以使用数组而不是散列图作为 O(n log n) 解决方案，或者可能 O(n) d 需要实现一个稳定的排序功能，同时提供元素的原始索引。

1 4 3 2 4 2 8 1 9
0 1 2 3 4 5 6 7 8 (indexes)

已排序：

1 1 2 2 3 4 4 8 9
0 7 3 5 2 1 4 6 8 (indexes)
--- ---   ---

现在，通过遍历排序的数组并根据重复索引排列插入每个元素的最后一次出现来构建一个新数组，而不是哈希映射。最终数组如下所示：

 1  4  3  2  4  2  8  1  9
-1 -1 -1 -1  1  3 -1  0 -1 (previous occurrence)

我们现在准备运行 pkpnd 的算法稍微修改一下：

arr = ... (from input)
map = previous occurrence array
i = 0
i_best = 0
j_best = 0
for j from 0 to length(arr) - 1 inclusive:
    if map[j] >= 0:
        i = max(i, map[j] + 1)

    if j - i > j_best - i_best:
        i_best = i
        j_best = j
return subarray(arr, i_best, j_best)

JavaScript代码：

function f(arr, map){
  let i = 0
  let i_best = 0
  let j_best = 0

  for (j=0; j<arr.length; j++){
    if (map[j] >= 0)
      i = Math.max(i, map[j] + 1)

    if (j - i > j_best - i_best){
       i_best = i
       j_best = j
    }
  }

  return [i_best, j_best]
}

let arr = [ 1, 4, 3, 2, 4, 2, 8, 1, 9]
let map = [-1,-1,-1,-1, 1, 3,-1, 0,-1]
console.log(f(arr, map))

arr = [ 1, 2, 2, 2, 2, 2, 1]
map = [-1,-1, 1, 2, 3, 4, 0]
console.log(f(arr, map))

Answer 4

我们可以使用哈希表（C#中的字典）

 public int[] FindSubarrayWithDistinctEntities(int[] arr)
    {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        Result r = new Result();   //struct containing start and end index for subarray
        int result = 0;
        r.st = 1;
        r.end = 1;
        for (int i = 0; i < arr.Length; i++)
        {               
            if (dic.ContainsKey(arr[i]))
            {
                int diff = i - (dic[arr[i]] + 1);
                if(result<diff)
                {
                    result = diff;
                    r.st = Math.Min(r.st, (dic[arr[i]] + 1));
                    r.end = i-1;                      
                }
                dic.Remove(arr[i]);
            }
            dic.Add(arr[i], i);
        }
        return arr.Skip(r.st).Take(r.end).ToArray();
    }

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

Algorithm for the largest subarray of distinct values in linear time

algorithm

performance

time

distinct-values