Сколько уникальных чисел в каждом возможном подсписке заданной длины

Question

Дается список чисел t. Дается число k - количество рассматриваемых чисел за 1 раз. Необходимо применить k к списку чисел и выяснить, сколько уникальных чисел содержится в каждой части списка.

Например:

[1,1,2,2],2 - значит, что нужно каждые два числа в списке проанализировать ([1,1], [1,2] и [2,2]), и получится тогда такой список уникальных чисел [1, 2, 1]

[1,1,1,1],4 - значит, что будет только один отрезок, длиной в 4 цифры и список уникальных чисел будет таким [1]

[1,2,3,2,2,2],3 - соответственно, отрезки по 3 числа ([1,2, 3], [2,3,2],[3,2,2] и [2,2,2]). В итоге получаем список униклаьныз чисел [3,2,2,1]

Решение у меня есть такое, но надо решить за O(n)

def count(t,k):
  n = len(t)
  windows = [] 
  pos = k-1
 
  for i in range(pos, n):
    newSet = set()
    for j in range(i, i-k, -1):
      newSet.add(t[j])
    
    windows.append(len(newSet))
 
  return windows

Answer 1

Не знаю как оценить скорость преобразования в set, но цикл идет О(n).

def count(t, k):
    result = []
    for i in range(len(t) - k + 1):
        temp = len(set(t[i:i + k])) # тут просто берем окно, преобразуем в set и берем его длинну.
        result.append(temp)
    return result
l = [1,2,3,2,2,2]
print(count(l, 3))

Answer 2

Я тут опять с Counter:

from collections import Counter

def uniq(t, k):
    res = []
    n = len(t)
    cnt = Counter()
    for i in range(min(n, k)):
        cnt[t[i]] += 1
    res.append(len(cnt))
    for i in range(k, n):
        cnt[t[i-k]] -= 1
        if cnt[t[i-k]] == 0:
            del cnt[t[i-k]]
        cnt[t[i]] += 1
        res.append(len(cnt))
    return res

print(uniq([1,2,3,2,2,2],3))

вывод:

>>[3, 2, 2, 1]

БЛОГ НА HUSL

Сколько уникальных чисел в каждом возможном подсписке заданной длины

Ответы (2 шт):