Почему мой лимит превышен по наиболее часто задаваемому вопросу [LEETCODE]?

Question

У меня есть следующий код для топ-кода Leetcode. Частый вопрос.

Допустимая сложность по времени меньше, чем o(nlogn), где n - размер массива

Не мойбольшой O сложность o(n)?Если так, почему я все еще превышаю ограничение по времени?

def topKFrequent(self, nums, k):
        output = {}
        outlist = []
        for item in nums:
            output[item] = nums.count(item)
        max_count = sorted(output.values(),reverse= True)[:k]
        for key,val in output.items():
            if val in max_count:
                outlist.append(key)
        return (outlist)

testinput: array [1,1,1,2,2,3,1,1,1,2,2,3] k = 2

выход теста: [1,2]

Ссылка на вопрос: https://leetcode.com/problems/top-k-frequent-elements/

Answer 1

Как уже упоминалось в другом ответе, ваш счет составляет O(n^2) сложность времени, из-за которой превышен ваш лимит времени.К счастью, python поставляется с объектом Counter в модуле collections, который будет делать то же самое, что описано в другом ответе, но в хорошо оптимизированном C-коде.Это снизит вашу временную сложность до O(nlogn).

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

from collections import Counter
from heapq import heappushpop, heapify


def get_most_frequent(nums, k):
    counts = Counter(nums)
    counts = [(v, k) for k, v in counts.items()]

    heap = counts[:k]
    heapify(heap)

    for count in counts[k:]:
        heappushpop(heap, count)

    return [k for v, k in heap]

Если вы должны вернуть элементы в любом конкретном порядке, вы можете отсортировать элементы k за O(klogk) время.что все равно приводит к такой же O(nlogk) сложности времени в целом.

Answer 2

Ваше решение - O(n^2), поэтому:

for item in nums:
    output[item] = nums.count(item)

Для каждого элемента в вашем массиве вы просматриваете весь массив, чтобы подсчитать количество одинаковых элементов.

Вместо этого вы можете получить счет в O(n), повторяя nums и добавляя 1 к счетчику каждого элемента, который вы найдете по ходу.

O(n log n) вконец придет от sorted(output.values(), reverse=True), потому что каждый общий алгоритм сортировки (включая Timsort) будет O(n log n).