Geek asks and answers

Sort an array of numbers with the total number of digits

Given an array of natural numbers, each number can be a different number of digits, but it is guaranteed that the total number of digits of all numbers is equal m.

For example, if there are three numbers:

2,3,1081 then m = 6.

I need an algorithm that sorts the numbers in an array in O(m).

I tried with radix sorting but that did not help me.

+3
source share
2 answers

First of all, you can use Bucket Sort to sort the array by the length of the digits of the digits and sort them into groups (group by the length of the digits). n(array size)<=m

===> this view will be O(n)<=O(m)

Then for each group of numbers (group by the length of the digits) you do radixsort O(m)

the result is that all numbers are sorted!

+3

Radix sort O(m). , , .

, " " (, 2- "5" ), -1, , .

"" "" , ( "-1" ).

, - , -1.
O(m+n), n<m - O(m)

+2
source

More articles:


All Articles