1

Дается список чисел 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

2 ответа 2

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]
1
  • @braflovsky Неужто не сработало? В условии не сказано про случай k>n, я пустой список возвращаю, а, может быть, нужно из одного элемента (изменил)
    – MBo
    9 окт 2020 в 7:06
0

Не знаю как оценить скорость преобразования в 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))
1
  • Система пишет, что слишком много времени занимает все равно(
    – braflovsky
    7 окт 2020 в 17:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.