Составить самое большое число из массива чисел
Вечером ребята решили поиграть в игру «Большое число». Даны числа. Нужно определить, какое самое большое число можно из них составить. Количество чисел не превосходит 100. Числа неотрицательные. Каждое не превосходит 1000. Нужно вывести самое большое число, которое можно составить из данных чисел.
Пример 1
Ввод
15 56 2
Вывод
56215
Пример 2
Ввод
1 783 2
Вывод
78321
Пример 3
Ввод
2 4 5 2 10
Вывод
542210
Вот написал код, но он не работает как нужно. Возможно слишком заморочено, но ничего проще в голову не приходит, как это еще можно сделать.
Пробовал считать суммы чисел - тоже не проходит.
Какие есть варианты? Уже часов 8 сижу с этой задачей.
/*
Сортирую вставками, в цикле while в проверке запускаю функцию comparator(),
в которой сравниваю текущее и прошлое значение.
*/
function getBigNumber(list){
for(let i = 0; i < list.length; i++){
const itemToInsert = list[i];
let j = i;
while(j > 0 && comparator(itemToInsert, list[j - 1])){
list[j] = list[j - 1];
j--;
}
list[j] = itemToInsert;
}
let result = '';
list.forEach(({ str }) =>
result += str)
console.log(result)
}
/*
Сравниваю текущее и прошлое число.
Если числа имеют одинаковую длину - сравниваю их как больше - меньше.
Если у них разная длина, запускаю функцию compare(), где разбиваю числа на
массив цифр. Если их первые числа разные, тогда смотрю какое больше больше,
это и верну как большее.
Если первые числа одинаковые, тогда цикл while отрежет первые цифры и
сравнение продолжится по следующим, while работает пока первые числа одинаковые
и хоть в каком то массиве больше чем 1 число.
Затем сравниваю первые числа массивов, где число больше, тот больше. Если в
одном из массивов 1 число, а в другом 2, тогда сравниваю первое число с последним.
Если последнее больше первого - значит оно больше.
*/
function comparator(current, prev){
const compare = (left, right) => {
const splittedLeft = left.split('');
const splittedRight = right.split('');
while(left[0] === right[0] && splittedLeft.length > 1 && splittedRight.length > 1){
splittedLeft.shift();
splittedRight.shift();
}
if(splittedLeft[0] > splittedRight[0] && splittedLeft.length >= 1 && splittedRight.length >= 1)
return left;
else if(splittedLeft[0] < splittedRight[0] && splittedLeft.length >= 1 && splittedRight.length >= 1)
return right;
else if(splittedLeft.length < splittedRight.length && splittedLeft[0] > splittedRight[splittedRight.length - 1])
return left;
else if(splittedLeft.length < splittedRight.length && splittedLeft[0] < splittedRight[splittedRight.length - 1])
return right
else if(splittedLeft.length > splittedRight.length && splittedRight[0] > splittedLeft[splittedLeft.length - 1])
return right;
else if(splittedLeft.length > splittedRight.length && splittedRight[0] < splittedLeft[splittedLeft.length - 1])
return left;
}
const splittedCurrent = current.split('');
const splittedPrev = prev.split('');
if(splittedCurrent.length === splittedPrev.length)
return Number(prev) - Number(current) > 0 ?
true : false;
else
return compare(prev, current) === prev ? true : false;
}
Ответы (2 шт):
Решал в своё время на Яве
class Solution {
public String largestNumber(int[] nums) {
String [] s = new String [nums.length];
int len=0;
boolean hasNonZero = false;
for (int i = 0; i < nums.length; i++) {
int n = nums[i];
if (n > 0) hasNonZero = true;
String t = String.valueOf(n);
len += t.length();
s[i] = t;
}
if (!hasNonZero) return "0";
Arrays.sort(s, (a,b) -> this.compare(b,a));
StringBuilder sb = new StringBuilder(len);
for (String t : s) {
sb.append(t);
}
return sb.toString();
}
// AB ABY ==> ABABY vs ABYAB
// AB > ABY if A > Y
private int compare(String a, String b) {
int a_len = a.length();
int b_len = b.length();
int len = a_len == b_len ? a_len : a_len + b_len;
for (int i=0; i < len; i++) {
char ac = i < a_len ? a.charAt(i) : b.charAt(i-a_len);
char bc = i < b_len ? b.charAt(i) : a.charAt(i-b_len);
if (ac == bc) continue;
return ac < bc ? -1 : 1;
}
return 0;
}
}
В общем, я честно пытался придумать нечто изящное, но в итоге все равно пришел к глупому решению без математики:
const foo = str => str.split(/\s+/).sort((a, b) => (b + a) - (a + b)).join('');
console.log(foo('15 56 2')); // --> 56215
console.log(foo('1 783 2')); // --> 78321
console.log(foo('2 4 5 2 10')); // --> 542210
console.log(foo('91 9')); // --> 991
console.log(foo('23 239')); // --> 23923
console.log(foo('23 23234')); // --> 2323423
Вроде работает, но удовлетворения решением нет((