Можно ли в общем случае сортировать линейное время?

Question

Я пытаюсь решить проблему в O (n) времени, когда, учитывая два передних итератора перед контейнером и задней частью контейнера, я хочу удалить все элементы в контейнере, которые не отображаются в наименее < это число> раз. Например, для вектора строк, таких как («john», «hello», «one», «yes», «hello», «one»), и я хотел удалить все элементы, которые появляются менее чем в 2 раза, конечный вектор затем будет содержать только («привет», «один»).

Я думал, что если бы я мог сортировать в O (n) время, я мог бы выполнить этот результат (в O (n) время), но мне тяжело это делать со строками, ints, chars, или что-либо еще (в общем). Я думаю об этом правильно, или есть более простой способ решить проблему?

Answer 1

Да, вы фактически не сортируете, а удаляете элементы.

1). Храните каждое слово в хешсет. 2). Поиск и добавление, если не в hashset.

Answer 2

Там нет необходимости, чтобы отсортировать

1) занесения std::unordered_map<string,vector<int>> indexOfStrings; - O (N)

2) Для каждого string которого vector size() < 2, удалить элемент - O (число делеций) < = O (N)

indexOfStrings - хранит индекс каждой видимости строки. Это позволяет быстро удалить из вектора без необходимости поиска.

Answer 3

Вам не нужно своего рода, вам просто нужно unordered_map:

unordered_map<string, int> counter; 
vector<string> newvec; 
for(string &s : v) { 
    if((++counter[s]) == 2) { 
     newvec.push_back(s); 
    } 
} 

Обратите внимание, что это C++ 11 код. (Спасибо @jogojapan за предложение улучшения кода).

Answer 4

Короткий ответ: нет. Сортировка на основе сравнения занимает O(n log n) времени. (Это может быть формально доказано.) Если вы знаете что-то о своем вводе (например, ввод распределяется равномерно случайным образом в пределах известного диапазона), то вы можете использовать известные алгоритмы, такие как сортировка ковша или сортировка радикса в O(n) времени. Вопреки @Mooing Duck, нет такой вещи, как сортировка в O(1) времени (это должно быть очевидно - вы должны посетить каждый элемент хотя бы один раз для любого алгоритма сортировки).

Однако, как отметили несколько других плакатов, ваша проблема не требует алгоритма сортировки ...