#arrays #algorithm #sorting #count #time-complexity
Вопрос:
существует m массивов, содержащих число в диапазоне 1-n. размер целых M групп равен n. средний размер(m1) размер(м2) … размер(Mn) = n массивы должны быть отсортированы и возвращены отдельно.
проблема в том, что она должна быть в O(n), а не в O(m n). если вы объединяете массивы и выполняете сортировку по количеству, вы получаете O(n), но как вы можете возвращать группы отдельно, а не в виде отсортированного массива всех n значений?
Комментарии:
1. Украсьте каждое число, чтобы указать, к какому массиву оно принадлежит (что равно O(n)), по радиусу отсортируйте украшенные числа (что равно O(n)), затем разделите на группы на основе оформления (что равно O(n)). Сумма = 3 * O(n) = O(n).
2. В этом случае
O(n) = O(m n), если вы не разрешите M включать массивы нулевой длины.