Description
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Examples:
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"Solution in Python
To solve the problem of arranging the numbers in such a way that they form the largest possible number, we can follow these steps:
- Convert the Numbers to Strings: Since we need to compare the concatenation results of the numbers, converting them to strings will allow us to perform these comparisons easily.
- Custom Sorting: We need to define a custom comparator for sorting the numbers. The idea is to compare two numbers
xandyby comparing the concatenated resultsx+yandy+x. Ifx+yis greater thany+x, thenxshould come beforey. - Handling Edge Cases: After sorting, if the largest number is
0, then all numbers are zero, and we should return “0”. - Concatenate the Result: Finally, concatenate the sorted numbers to form the largest number.
Python
from typing import List
from functools import cmp_to_key
class Solution:
def largestNumber(self, nums: List[int]) -> str:
# Custom comparator function
def compare(x, y):
# Compare concatenated results
if x + y > y + x:
return -1 # x should come before y
elif x + y < y + x:
return 1 # y should come before x
else:
return 0 # x and y are equal in terms of concatenation order
# Convert all integers to strings for easy comparison
nums_str = list(map(str, nums))
# Sort the list with the custom comparator
nums_str.sort(key=cmp_to_key(compare))
# Join the sorted list into a single string
largest_num = ''.join(nums_str)
# Edge case: if the largest number is '0', return '0'
if largest_num[0] == '0':
return '0'
return largest_numExplanation
- Comparator Function:
- The
comparefunction is defined to compare two stringsxandy. - It returns
-1ifx + yis greater thany + x, meaningxshould come beforeyin the sorted order. - It returns
1ifx + yis less thany + x, meaningyshould come beforex. - It returns
0if both concatenated results are equal.
- The
- Conversion to Strings:
- The list of integers is converted to a list of strings using
map(str, nums).
- The list of integers is converted to a list of strings using
- Sorting:
- The list of strings is sorted using the custom comparator.
cmp_to_key(compare)converts the comparator function to a key function suitable forsort().
- The list of strings is sorted using the custom comparator.
- Concatenation and Edge Case:
- The sorted list of strings is joined into a single string using
''.join(nums_str). - If the resulting string starts with ‘0’, this means all numbers were zeros, and thus the result should be ‘0’.
- The sorted list of strings is joined into a single string using
This approach ensures that the numbers are arranged in a way that forms the largest possible number when concatenated.
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
// Custom comparator function
const compare = (x, y) => {
// Compare concatenated results
const order1 = x + y;
const order2 = y + x;
if (order1 > order2) {
return -1; // x should come before y
} else if (order1 < order2) {
return 1; // y should come before x
} else {
return 0; // x and y are equal in terms of concatenation order
}
};
// Convert all integers to strings for easy comparison
const numsStr = nums.map(String);
// Sort the list with the custom comparator
numsStr.sort(compare);
// Join the sorted list into a single string
const largestNum = numsStr.join('');
// Edge case: if the largest number is '0', return '0'
if (largestNum[0] === '0') {
return '0';
}
return largestNum;
};Solution in Java
Java
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public String largestNumber(int[] nums) {
// Convert the integers to strings for easy comparison
String[] numsStr = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
numsStr[i] = String.valueOf(nums[i]);
}
// Define a custom comparator
Comparator<String> customComparator = new Comparator<String>() {
@Override
public int compare(String x, String y) {
// Compare concatenated results
String order1 = x + y;
String order2 = y + x;
return order2.compareTo(order1); // y+x compared to x+y (descending order)
}
};
// Sort the array with the custom comparator
Arrays.sort(numsStr, customComparator);
// Handle the edge case where the largest number is '0'
if (numsStr[0].equals("0")) {
return "0";
}
// Join the sorted strings into a single string
StringBuilder largestNum = new StringBuilder();
for (String numStr : numsStr) {
largestNum.append(numStr);
}
return largestNum.toString();
}
}Solution in C#
C#
using System;
using System.Linq;
public class Solution {
public string LargestNumber(int[] nums) {
// Convert the integers to strings for easy comparison
string[] numsStr = nums.Select(num => num.ToString()).ToArray();
// Define a custom comparator
Array.Sort(numsStr, (x, y) => {
// Compare concatenated results
string order1 = x + y;
string order2 = y + x;
return order2.CompareTo(order1); // y+x compared to x+y (descending order)
});
// Handle the edge case where the largest number is '0'
if (numsStr[0] == "0") {
return "0";
}
// Join the sorted strings into a single string
return string.Concat(numsStr);
}
}