179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

179. Наибольшее число

Задан массив неотрицательных целых чисел. Расположите их так, чтобы образовалось наибольшее число.

Например, из массива чисел [3, 30, 34, 5, 9] наибольшее можно получить число 9534330.

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

// C++

class Solution {

public:

string largestNumber(vector<int>& nums) {

}

};

// Java

public class Solution {

public String largestNumber(int[] nums) {

}

}

РЕШЕНИЕ

сортировка - компаратор

Анализ алгоритма

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

Если массив чисел содержит множество нулей, как например [0, 0, 0], то ответом должна быть строка “0”, а не “000”.

Реализация алгоритма

int f(string a, string b)

{

return a + b > b + a;

}

class Solution

{

public:

string largestNumber(vector<int> &num)

{

vector<string> s;

char temp[1000];

Преобразуем массив чисел в массив строк s.

for(int i = 0; i < num.size(); i++)

{

sprintf(temp,"%d",num[i]);

s.push_back((string)temp);

}

Отсортируем массив строк согласно компаратору f.

sort(s.begin(),s.end(),f);

Произведем конкатинацию строк массива s в одну строку.

string res;

for(int i = 0; i < s.size(); i++)

res = res + s[i];

Удалим ведущие нули.

while ((res[0] == '0') && (res.size() > 1))

res.erase(res.begin());

return res;

}

};

Java реализация

public class Solution

{

public String largestNumber(int[] nums)

{

String[] arr = new String[nums.length];

for(int i = 0; i < nums.length; i++)

arr[i] = String.valueOf(nums[i]);

Arrays.sort(arr, new Comparator<String>()

{

public int compare(String a, String b)

{

return (b+a).compareTo(a+b);

}

});

String res = "";

for(int i = 0; i < arr.length; i++)

res += arr[i];

/*

for(String temp : arr)

res += temp;

*/

if (res.charAt(0) == '0') res = "0";

return res;

}

}

Java реализация – отдельный компаратор

class Solution

{

public static class MyFun implements Comparator<String>

{

public int compare(String a, String b)

{

return (b+a).compareTo(a+b);

}

}

public String largestNumber(int[] nums)

{

String[] arr = new String[nums.length];

for(int i = 0; i < nums.length; i++)

arr[i] = String.valueOf(nums[i]);

Arrays.sort(arr, new MyFun());

String res = "";

for(int i = 0; i < arr.length; i++)

res += arr[i];

if (res.charAt(0) == '0') res = "0";

return res;

}

}