Проблема

Given a list of non negative integers, arrange them such that they form the largest number.
Example: 
Given [3, 30, 34, 5, 9], the largest formed number is 9534330. 
The result may be very large, so you need to return a string instead of an integer.

Категория: Массивы

Процесс решения

Упорядочивание массива в определенном порядке должно вызвать идею реализации нашей стратегии пользовательской сортировки.

В Java это означает реализацию интерфейса Comparable.

Таким образом, эта проблема не очень сложна, но при реализации стратегии сортировки легко допустить ошибку.

Давайте посмотрим на несколько примеров желаемых результатов нашей реализации сортировки, учитывая, что мы хотели бы отсортировать их в обратном порядке (9 ‹8 означает, что мы получим результат 98):

Inputs: 1 and 1, output: 1 then 1
Inputs: 25 and 27, output: 27 then 25
Inputs: 3 and 30, output: 3 then 30
Inputs: 12 and 121, output: 12 then 121

Здесь есть небольшая хитрость, надеюсь, вы ее заметили.

Самое простое решение - объединить (не складывать, объединять) два целых числа обоими способами и сравнить их:

For clarity, the first input is in bold.
Inputs: 1 and 1
Lexicographically 11 <= 11, output is 1 then 1
Inputs: 25 and 27
Lexicographically 2527 < 2725, output is 27 then 25
Inputs: 3 and 30
Lexicographically 303 < 330, output is 3 then 30
Inputs: 12 and 121
Lexicographically 12112 < 12121, output is 12 then 121

Возможная реализация на Java:

Чтобы вернуть действительное целочисленное представление, нам просто нужно убедиться, что ввод 0 0 0 0 возвращает 0, а не 0000. Это делается путем проверки, равен ли первый элемент массива containers 0.

Сложность по времени составляет O (n log (n)) с n количеством элементов списка, поскольку мы должны отсортировать массив. Сложность пространства равна O (n) (линейная), где n также представляет количество элементов, поскольку нам нужно создать еще один массив для реализации стратегии сортировки.

дальнейшее чтение