Перейти к содержанию

Название задания

Ссылка с заданием на литкоде

Описание

Переставьте полученный список чисел nums так, чтобы они образовывали максимальное число и вернуть это число.

Поскольку число может быть очень большим вернуть его необходимо в виде строки.

Пример 1:

Входные данные: nums = [10, 2]
Выходные данные: "210"
Объяснение: число 210 больше чем 102

Пример 2:

Входные данные: nums = [3, 30, 34, 5, 9]

Выходные данные: "9534330"

Пример 3:

Входные данные: nums = [0, 0]
Выходные данные: "0"

Идея решения

Самым простым решением было бы проверить все возможные комбинации. Неэффективность такого подхода требует найти другое решение. Более эффективным будет провести такую операцию не со всеми числами, а только с парами при сортировке.

Алгоритм решения

Для решения достаточно верно отсортировать наш список чисел. "Верным" будет ставить вперёд то число которое при "соединении" со вторым даёт большее число.

Таким образом наш алгоритм выглядит так:
1. приведём все числа к строкам для удобства
2. сортируем числа используя дополнительную функцию _cmp
3. функция _cmp сравнивает два варианта конкатенации полученных строк
4. если первое число 0, то возвращаем "0", иначе собираем все строки в одну

Сложность

  • По времени: \(O(N log N)\) n = len(nums)

Наш алгоритм совершает три основных действия.
1. Преобразование чисел в строки, что требует прохода по всему списку чисел, требуя \(O(N)\)
2. Сортировка списка чисел, представленных в виде строк. Сама сортировка достаточно эффективно реализованна в языке и требует в среднем \(n log n\). Однако, для каждого значения мы вызываем функцию _cmp, что добавляет время на конкатенацию строк. Общее время этого этапа будет \(O(NM log N)\), где M равно средней длине строки в result.
3. Для получения ответа мы должны собрать строки в одну, что требует прохода по всем строкам и по каждой строке, что требует \(O(MN)\)

Общую сложность по времени \(O(N + NM log N + MN)\) можно упростить до \(O(NM log N)\), кроме того по условию M не может быть больше 100, так что это значение можно считать константным.

  • По памяти: \(O(N)\) n = len(nums) Каждый из этапов описаных выше требует выделения памяти равное размеру полученного списка.

Код решения:

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        result = map(str, nums)
        result = sorted(result, key=cmp_to_key(self._cmp))

        return '0' if result[0] == '0' else ''.join(result)

    def _cmp(self, s1: str, s2: str) -> int:
        return -1 if s1 + s2 > s2 + s1 else 1

impl Solution {
    pub fn largest_number(nums: Vec<i32>) -> String {
        let mut result: Vec<String> = nums.iter().map(|num| num.to_string()).collect();
        result.sort_by(|a, b| Solution::_cmp(b, a));

        if result[0] == "0" {
            "0".to_string()
        } else {
            result.join("")
        }
    }

    fn _cmp(a: &str, b: &str) -> std::cmp::Ordering {
        let ab = a.to_string() + b;
        let ba = b.to_string() + a;

        ab.cmp(&ba)
    }
}