У меня проблема со спецификацией, которую нам дали.Нам дан двумерный массив слов и их частота, и мы должны отобразить слова kTop, отсортированные сначала по их частоте, а затем по их алфавитному порядку.Входной массив уже отсортирован в алфавитном порядке. И все это должно быть сделано в O (NLogK) временной сложности и O (KM) пространственной сложности.
Я разобрался, как извлечь первые k слов.Используя минимальную кучу.Где я сначала добавляю k элементов в кучу.И чем запустить цикл для nk, где я сравниваю, если значение корня меньше, чем значение в цикле.Если это так, я извлекаю корень и помещаю значение в цикл.После цикла я просто использую сортировку для сортировки кучи по частоте.
Пока у меня две проблемы с этим алгоритмом.Прежде всего, если K достаточно велико, чтобы оно также содержало минимальную частоту.Так как мой исходный массив отсортирован по алфавиту.Этот алгоритм делает так, чтобы я выдавал слово, которое должно быть в последней куче.
Секон всего моего heapsort не стабилен.Так что иногда он сортируется по частоте, но алфавитный порядок перепутан.Я пытался изменить heapsort, но это просто пошло бесконечным циклом.И я также попытался использовать сортировку вставки, которая дала правильный ответ, но превышает сложность по времени.
Спасибо за чтение.Буду признателен за любую помощь.