Число различных подпоследовательностей длины 3 в массиве длины n - PullRequest
Новая
       30

Число различных подпоследовательностей длины 3 в массиве длины n

0 голосов
/ 05 июня 2018

Как рассчитать количество различных подпоследовательностей длины 3 (или вообще длины k < n) в массиве длины n?

Примечание: Две подпоследовательности считаются разными, если порядок элементов в них различен.

Пример: Предположим, массив A = [1, 2, 1, 1], тогда ответ должен быть 3, потому что есть только три различных подпоследовательности длины 3 как показано ниже: 

[1, 1, 1]
[1, 2, 1]
[2, 1, 1]

Размер массива n <= 10^5, каждый элемент в массиве A_i <= n.

Мой подход:

Я понял фигурупринудительный подход, т. е. взять кортежи длиной 3 и вставить их в карту.Но это не эффективное пространство / время.

Редактировать : Это был вопрос для интервью, в котором говорилось, что для k = 3 ожидаемая сложность времени и пространства составляет O(n).

Ответы [ 2 ]

0 голосов
/ 05 июня 2018

Вот немного другой дубль.Мы можем думать о количестве способов, которыми элемент, m, может быть k th в подпоследовательности как сумма всех способов, которыми предыдущее вхождение любого элемента (включая m) может быть (k-1) th.Однако, когда мы движемся вправо, единственное необходимое обновление - для m;остальные суммы остаются постоянными.

Например, 

// We want to avoid counting [1,1,1], [1,2,1], etc. twice
[1, 2, 1, 1, 1]

(для удобства выведите массив вертикально) 

            <-  k  ->
[1,  ->  1: [1, 0, 0]
 2,  ->  2: [1, 1, 0]
 1,  ->  1: [1, 2, 1]
 1,  ->  1: [1, 2, 3]
 1]  ->  1: [1, 2, 3]

Теперь, если мы добавили еще один элемент, скажем 3, 

...
 3]  ->  3: [1, 2, 3]

 // 1 means there is one way
 // the element, 3, can be first

 // 2 means there are 2 ways
 // 3 can be second: sum distinct
 // column k[0] = 1 + 1 = 2

 // 3 means there are 3 ways
 // 3 can be third: sum distinct
 // column k[1] = 2 + 1 = 3

Отличная сумма k[2] столбец: 

0 + 3 + 3 = 6 subsequences

[1,2,1], [2,1,1], [1,1,1]
[1,1,3], [2,1,3], [3,2,1]

Отличная сумма для каждого столбца может быть обновлена ​​в O(1) за итерацию.Суммы k для текущего элемента (мы обновляем один список для каждого элемента), принимают O(k), что в нашем случае равно O(1).

Код JavaScript: 

function f(A, k){
  A.unshift(null);
  
  let sumDistinct = new Array(k + 1).fill(0);
  let hash = {};

  sumDistinct[0] = 1;

  for (let i=1; i<A.length; i++){
    let newElement;
    
    if (!hash[A[i]]){
      hash[A[i]] = new Array(k + 1).fill(0);
      newElement = true;
    }
    
    let prev = hash[A[i]].slice();

    // The number of ways an element, m, can be k'th
    // in the subsequence is the sum of all the ways
    // the previous occurence of any element
    // (including m) can be (k-1)'th
    for (let j=1; j<=k && j<=i; j++)
      hash[A[i]][j] = sumDistinct[j - 1];

    for (let j=2; j<=k && j<=i; j++)
      sumDistinct[j] = sumDistinct[j] - prev[j] + hash[A[i]][j];

    if (newElement)
      sumDistinct[1] += 1;

    console.log(JSON.stringify([A[i], hash[A[i]], sumDistinct]))
  }

  return sumDistinct[k];
}

var arr = [1, 2, 1, 1, 1, 3, 2, 1];

console.log(f(arr, 3));
0 голосов
/ 05 июня 2018

Как часто бывает в случае проблем с собеседованием, есть решение для динамического программирования.Пусть T(m, k) будет количеством различных длин- k подпоследовательностей первых m элементов.Затем, предполагая, что индексирование на основе ввода по одному вводится A, мы получаем двумерное повторение 

T(m, 0) = 1
T(m, k) = T(m-1, k) + T(m-1, k-1) -
          ^^^^^^^^^   ^^^^^^^^^^^
     A_m not chosen   A_m chosen

            { T(i-1, k-1), if i < m is the maximum index where A_i = A_m
            { 0,           if no such index exists

. Вычтенный член гарантирует, что мы не будем считать дубликаты;см. https://stackoverflow.com/a/5152203/2144669 для более подробного объяснения.

Время выполнения (с хэш-картой, поддерживающей крайнее правое вхождение каждого видимого символа) составляет O(k n), что составляет O(n) для k = 3.

...