4
Я знаю, что мы можем найти k-наибольшее число из п неупорядоченных чисел в 2 способами:Можно ли найти k-наибольшие числа из n несортированных целых чисел с временной сложностью O (n) и пространственной сложностью O (k)?
- Используйте алгоритм, как быстро выбрать, чтобы найти k-ю наибольшее число, то мы можем получить к-наибольшее число , Сложность времени - O (n), а пространственная сложность - O (n)
- Используйте кучу для хранения k-наибольших чисел и итерации через n целых чисел, а затем добавьте в кучу соответствующие целые числа. Сложность времени O (nlogk) и пространство сложность O (к)
Предположим, п целые числа в потоке, и мы не имеем случайного доступа к ним
Я хочу знать это можно найти k-наибольшие числа из n несортированных целых чисел с временной сложностью O (n) и пространственной сложностью O (k)?
Почему вы считаете быстрый выбор, чтобы иметь пространство сложность O (N). Он имеет сложность памяти сложения O (1) (при условии, что вы можете переустановить ввод) –
Это выполнимо. См. Http://link.springer.com/chapter/10.1007%2FBFb0015429 Используя этот алгоритм, вы можете найти k-е наибольшее число в линейном времени с постоянным количеством дополнительных переменных. –