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

Question

我试图想出一个快速算法，给出的长度为n的任何阵列，获得不同值的最大子数组。

例如，不同值的最大子阵列

[1, 4, 3, 2, 4, 2, 8, 1, 9]

将会

[4, 2, 8, 1, 9]

这是我目前的解决方案，我认为它运行在O（N ^ 2）。这是因为check_dups以线性时间运行，它被称为每次J或我的增量。

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

考虑寻找最大的不同值的子阵列在一个特定的指数j结束的问题。从概念上讲，这是简单的：开始arr[j]，你往后走，包括所有元素，直到找到一个副本。

让我们用这种直觉来解决这个问题，从j所有0高达length(arr)。我们需要知道，在迭代，多远后面我们可以去之前，我们找到一个重复的任何一点。也就是说，我们需要知道至少i这样subarray(arr, i, j)包含不同的值。 （我假设subarray对待指数的包容性。）

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

伪代码：

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 2

我们可以适应pkpnd算法使用数组而不是哈希映射为O(n log n)溶液或潜在的，如果你的数据允许的O(n)稳定的排序O(n)，但你需要实现一个稳定的排序功能，还提供了元素的原始指标。

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 3

我们可以（在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();
    }

Answer 4

每添加数HashSet的，如果它是不是已经在里面。 HashSet的的插入和搜索都是O（1）。所以，最终的结果将是为O（n）。