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 that you have read and understand our privacy policy and code of conduct.

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