Algorithm
Problem Name: 179. Largest Number
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.
Example 1:
Input: nums = [10,2] Output: "210"
Example 2:
Input: nums = [3,30,34,5,9] Output: "9534330"
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(int a, int b) {
char stra[N] = { 0 };
char strb[N] = { 0 };
sprintf(stra, "%d", a);
sprintf(strb, "%d", b);
char aplusb[N + N] = { 0 };
char bplusa[N + N] = { 0 };
strcpy(aplusb, stra);
strcat(aplusb, strb);
strcpy(bplusa, strb);
strcat(bplusa, stra);
return strcmp(aplusb, bplusa);
}
void quicksort(int *nums, int left, int right) {
if (left > right) return;
int i = left;
int j = right;
int pivot = nums[left];
while (i < j) {
while (i < j && compare(nums[j], pivot) <= 0) j--;
nums[i] = nums[j];
while (i < j && compare(nums[i], pivot) >= 0) i++;
nums[j] = nums[i];
}
nums[i] = pivot;
quicksort(nums, left, i - 1);
quicksort(nums, i + 1, right);
}
char* largestNumber(int* nums, int numsSize) {
quicksort(nums, 0, numsSize - 1);
char *ans = (char *)calloc(numsSize * N, sizeof(char));
int i;
for (i = 0; i < numsSize; i++) {
char buf[N] = { 0 };
sprintf(buf, "%d", nums[i]);
strcat(ans, buf);
}
/* skip leading zeros */
while (*ans == '0' && *(ans + 1) == '0') ans++;
return ans;
}
int main() {
int nums0[] = { 3, 30, 34, 5, 9 };
printf("%s\n", largestNumber(nums0, sizeof(nums0) / sizeof(nums0[0])));
int nums1[] = { 0, 0 };
printf("%s\n", largestNumber(nums1, sizeof(nums1) / sizeof(nums1[0])));
return 0;
}
Input
nums = [10,2]
Output
"210"
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String largestNumber(int[] nums) {
String largestNum = Arrays.stream(nums)
.boxed()
.map(String::valueOf)
.sorted((o1, o2) -> (o2 + o1).compareTo(o1 + o2))
.collect(Collectors.joining(""));
return largestNum.charAt(0) == '0' ? "0" : largestNum;
}
}
Input
nums = [10,2]
Output
"210"
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const largestNumber = function(nums) {
const arr = nums
.map(v => v.toString())
.sort((a, b) => (a + b < b + a ? 1 : -1))
.join("");
return arr[0] === "0" ? "0" : arr;
};
Input
nums = [3,30,34,5,9]
Output
"9534330"
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestNumber(self, nums):
def partition(l, r):
j = l
for i in range(l + 1, r + 1):
if nums[i] + nums[l] >= nums[l] + nums[i]:
j += 1
nums[j], nums[i] = nums[i], nums[j]
nums[l], nums[j] = nums[j], nums[l]
return j
def quickSort(l, r):
if l < r:
m = partition(l, r)
quickSort(l, m - 1)
quickSort(m + 1, r)
nums = [str(num) for num in nums]
quickSort(0, len(nums) - 1)
return str(int("".join(nums)))
Input
nums = [3,30,34,5,9]
Output
"9534330"
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Linq;
using System.Text;
namespace LeetCode
{
public class _0179_LargestNumber
{
public string LargestNumber(int[] nums)
{
if (nums.Length == 0) return string.Empty;
if (nums.Length == 1) return nums[0].ToString();
var numsStr = nums.Select(num => num.ToString()).ToArray();
Array.Sort(numsStr, (a, b) => (b + a).CompareTo(a + b));
if (numsStr[0] == "0") return "0";
var sb = new StringBuilder();
foreach (var str in numsStr)
sb.Append(str);
return sb.ToString();
}
}
}
Input
nums = [10,2]
Output
"210"