Алгоритм наибольшего подмассива различных значений в линейном времени

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

Мы можем использовать Hashtable (словарь в 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 2

Рассмотрим проблему поиска наибольшего однозначного подмассива , заканчивающегося определенным индексом 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).Мы можем вычислить lastOccurrence за O (1) время с помощью 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 3

Мы можем адаптировать алгоритм 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 4

Добавьте каждый номер в Hashset, если его еще нет. Вставка и поиск Hashset оба O (1). Таким образом, окончательный результат будет O (n).