Блог

У меня есть список целых чисел, которые представляют, сколько раз использовался элемент, и мне нужно найти следующий номер в последовательности, который использовался наименьшее количество раз (его может даже не быть в списке)

Количество элементов является динамическим, в примере используется 9, но это может быть. Кроме того, количество раз, когда он может появляться, также является динамическим.

We have X items, all of which are allowed to be used y times

Пример.

У нас есть 9 элементов, оба из которых разрешено использовать 2 раза, но их следует использовать по порядку.

 [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]
  

приведенное выше должно возвращать 3 в качестве следующего доступного элемента

 [1, 2, 3, 4, 5]
  

приведенное выше должно возвращать 6 в качестве следующего доступного элемента

 [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  

приведенное выше ничего не должно возвращать, поскольку больше нет доступных

У меня уже есть функция, которая проверяет, отображается ли число при максимальном количестве использований

 def is_item_available(item_number: int, uses: int, used_items: List):
    """Check if the item is available.
    Args:
        item_number (int): item number to be checked
        uses (int): number of uses allowed
        used_items (list): list of items currently used in a session
    Returns:
        bool: returns True if used item count is less than the uses number
    """
    return used_items.count(item_number) < uses
  

Я думаю, что эта функция работает, если числа гарантированно будут от 1 до 9:

 def next_item(used_items):
    if (used_items[-1] == 9 and len(used_items) == 18):
        return "nothing"
    elif (used_items[-1] == 9):
        return 1
    else:
        return used_items[-1]   1

  

Наиболее оптимальным решением было бы использовать минимальную кучу для хранения оперативных данных и извлечения верхней части кучи:

 import collections, heapq

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

## Counter will maintain the count of each element in the list
counter = collections.Counter(lst)

## We now create a min-heap with (counter.count, list.val) as elements
heap = [(value, key) for key,value in dict(counter).items()]

## Now fetch the top element from the min-heap. By definition, this would correspond to the minimum list.val with minimum count

smallest_element = heapq.nsmallest(1, heap)

## If the list.val is already been used twice, return "None" else return the list.val 
if smallest_element[0] > 1:
  return None
return smallest_element[1]