Учитывая массив натуральных чисел, каждое число может быть разным числом цифр, но гарантировано, что общее количество цифр всех чисел вместе составляет m.Сортировка массива чисел с общим количеством цифр
Например, если через три числа:
2,3,1081 then m = 6.
Мне нужен алгоритм, который сортирует числа в массиве в O(m).
Я пробовал с сортировкой по основанию, но это не полезно для меня.
Прежде всего, вы можете использовать Bucket Sort для сортировки массива по номерам цифр длины и порядка их группы (группа цифр длиной). n (размер массива) <=m
===> такого рода будет O(n)<=O(m)
Тогда для каждой группы чисел (группа цифр длиной) вы RadixSort O(m)
результата в том, что все номера сортируется!
Radix sort может решить эту проблему в O(m). Сделайте сортировку радикса, начиная с наименее значимого бита, и переместите торренты на самый значительный бит итеративно.
Всякий раз, когда вы сталкиваетесь с «не существующей цифрой» (например, 2-я итерация для числа «5»), обрабатывайте ее как -1, поэтому она будет первой в массиве, сгенерированном этой итерацией.
После каждого «раунда» уменьшите размер массива и «обрезайте» все числа, которые вы только что прошли (для этой итерации вы просто считались «-1»).
Это требует проверки каждой цифры в каждом элементе ровно один раз, а кроме того - для каждого элемента один раз, когда вы обрабатываете его как -1.
Это дает O(m+n) сложности, а так n<m - это O(m)
@dasblinkenlight. Третий «абзац» в ответе затрагивает эту проблему. После того, как вы обрабатываете число один раз как «-1», вы можете обрезать массив - префикс его, который начинается с -1, уже отсортирован.В вашем примере вы сначала сделаете итерацию для всех 501 номеров, затем выполните вторую итерацию, обрабатывая 500 чисел как «-1», а после второй итерации - вы можете обрезать массив и продолжить поиск в подмассиве 'а [500: 501]'. Больше нет доступа для элементов 'a [0: 500]' - этот подмассива сортируется, и каждый элемент находится там, где он должен быть. – amit
@dasblinkenlight (cont) - так что вам нужно изучить 1000 цифр, и для каждого номера один раз обрабатывайте его как -1, что дает вам 1000 + 501 <= 2 * 1000 – amit
@dasblinkenlight Не уверен, что вы имеете в виду, это вариант сортировки счисления, и я сортирую каждый раз по одной цифре. Каждое число с цифрами «k» будет обрабатываться точно «k + 1» раз, каждый раз используя в нем другую цифру. – amit
'но это не полезно для меня' почему? описывая, что не так, поможет нам понять вашу проблему. – amit
, потому что для radix мне нужно знать цифры цифр чисел – user2068793
Интересно, как это возможно в 'O (m)'. Представьте ситуацию, 'm = 1.000.000', и каждое число состоит только из одной цифры. Очевидно, что для сортировки вам придется применить обычный алгоритм сортировки, который не может быть «O (m)» (поскольку в этом случае «m» равно количеству элементов массива) - только «O (m log (m)) '. Думаю, это худший случай, но все же - вот почему я сомневаюсь. Или вам нужно будет использовать дополнительное пространство (но это зависит от сложности) –