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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
复制代码

给出一系列正整数，对这些数进行排列，使其拼凑出一个尽可能大（最大）的数。

例如，给出[3, 30, 34, 5, 9]，则这些数所能拼凑出的最大数字是 9534330。

注：给出的数组元素数量不定，结果可能非常非常大，所以你需要将结果作为字符串返回而不是int类型的整数（尤其是对于那些强类型的语言）
复制代码

var largestNumber = function(nums) {
	return [].join.call(arguments)
	.split(',')
	.sort(function(a,b){
		return b+a > (a+b) ? 1 : -1
	})
	.join('').replace(/^0+(.)/,'$1')
}
复制代码

#*&cls&gawk -f "%~f0"&pause&exit

BEGIN{
    str="3,30,34,5,9"
    split(str,a,",");
    if(length(a)==1){
        print a[1];
    }else{
        if(str~/^[0,]*$/){
            print 0;
        }else{
            for(i=1;i<=length(a);i++){
                if(a[i]~/^0+[1-9][0-9]*$/){
                    sub(/^0+/,"",a[i]);
                }else{
                    if(a[i]~/^0+$/)sub(/0+/,"0",a[i]);
                }
                t=a[i];
                j=i-1;
                while(j>=1&&(!comp(a[j],t))){
                    a[j+1]=a[j];
                    j--;
                }
                a[j+1]=t;
            }
            for(i=1;i<=length(a);i++)s=s""a[i];
            print s;
        }
    }
}
function comp(a,b){return (a""b)*1>(b""a)*1?1:0;}
复制代码

@echo off&setlocal enabledelayedexpansion
set "s=89 89891 830 8308 8300 89899 9 999999999999999999999 9999999999999999999999999999"
for %%a in (%s%) do (
    set "a=%%a%%a%%a%%a%%a%%a%%a%%a%%a!random!"
    set #!a!=%%a
)
(for /f "tokens=2 delims==" %%a in ('set # ^|sort /r') do set/p.=%%a)<nul
pause
复制代码

var largestNumber = function(nums) {
    var arr = [];
    [].forEach.call(arguments,function(a){a.map?[].push.apply(arr,a):arr.push(a)})
	return arr
    	.sort(function(a,b){
    		return ''+b+a > ''+a+b ? 1 : -1
    	})
    	.join('').replace(/^0+(.)/,'$1')
}
复制代码

char* largestNumber(int* nums, int numsSize) {
	struct struct_num{
		int digit;
		int number;
	};

	struct struct_num *group[10][100], *pg, *pg2;
	int group_count[10]={0,0,0,0,0,0,0,0,0,0};
	int i,j,k;
	int number,index,digit;
	char output[10000]="0";
	char *p=output;

	const char itoa_map[11]="0123456789";

	for(i=numsSize;i--;){
		number = nums[i];

		for(digit=10;number>=digit;digit*=10){}
		index = number/(digit/10);

		pg=(struct struct_num *)malloc(sizeof(struct struct_num));

		group[index][group_count[index]++]=pg;
		(pg)->number = number;
		(pg)->digit = digit;
	}

	for(i=10;i--;){
		for(j=group_count[i];j-->0;){
			pg = group[i][j];

			for(k=j;k-->0;){
				pg2 = group[i][k];
				if(
					((long long) pg->number * pg2->digit+pg2->number)< ((long long) pg2->number * pg->digit + pg->number)
				){
					* (long long*) pg ^= * (long long*) pg2;
					* (long long*) pg2 ^= * (long long*) pg;
					* (long long*) pg ^= * (long long*) pg2;
				}
			}
		}
		for(j=group_count[i];j--;){
			pg = group[i][j];
			number = pg->number;
			digit = pg->digit / 10;
			while(digit >= 1){
				*p++ = itoa_map[number / digit % 10];
				digit /= 10;
			}
			free(pg);
		}
	}
	if(output[0]=='0')return "0";

	*p='\0';

	return output;
}
复制代码

#define _CRT_SECURE_NO_WARNINGS

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int Comparer(char * strLeft, char * strRight)
{
	char * cmpLeft = strLeft;
	char * cmpRight = strRight;
	for (;; ++cmpLeft, ++cmpRight)
	{
		char chLeft = *cmpLeft;
		char chRight = *cmpRight;

		if (!chLeft && !chRight)
			return 0;

		if (!chLeft)
		{
			cmpLeft = strRight;
			chLeft = *cmpLeft;
		}

		if (!chRight)
		{
			cmpRight = strLeft;
			chRight = *cmpRight;
		}

		if (chLeft == chRight)
			continue;
		else
			return chLeft > chRight;
	}
	return 0;
}

void QS_Swap(char ** left, char ** right)
{
	char * tmp = *left;
	*left = *right;
	*right = tmp;
}

int QS_Partition(char ** arr, int lo, int hi)
{
	char * pivot = arr[hi];
	int i = lo;

	for (int j = lo; j < hi; ++j)
	{
		if (Comparer(arr[j], pivot))
		{
			QS_Swap(&arr[i], &arr[j]);
			++i;
		}
	}
	QS_Swap(&arr[i], &arr[hi]);
	return i;
}

void QS_Sort(char ** arr, int lo, int hi)
{
	if (lo < hi)
	{
		int p = QS_Partition(arr, lo, hi);
		QS_Sort(arr, lo, p - 1);
		QS_Sort(arr, p + 1, hi);
	}
}

void QSort(char ** arr, int len)
{
	QS_Sort(arr, 0, len - 1);
}

char * largestNumber(int * nums, int numsSize)
{
	char * strBuf = (char*)malloc(numsSize * 16);
	char ** strNums = (char**)malloc(sizeof(char*) * numsSize);
	int szTotalLen = 0;
	for (int i = 0; i < numsSize; ++i)
	{
		//char * strItem = _itoa(pNums[i], strBuf, 10);
		sprintf(strBuf, "%d", nums[i]);
		char * strItem = strBuf;

		int slen = strlen(strItem);
		szTotalLen += slen;

		strBuf += slen + 1;
		strNums[i] = strItem;
	}

	QSort(strNums, numsSize);

	strBuf = (char*)malloc(szTotalLen + 1);
	char * strRes = strBuf;
	for (int i = 0; i < numsSize; ++i)
	{
		char * strItem = strNums[i];
		strcpy(strBuf, strItem);
		strBuf += strlen(strItem);
	}

	while (*strRes == '0' && *(strRes + 1))
		++strRes;

	return strRes;
}

int main()
{
	int nums[] = { 0, 0, 1 };
	char *s = largestNumber(nums, sizeof(nums) / sizeof(nums[0]));
	printf("%s", s);

	return 0;
}
复制代码

void q_sort(char* arr[], const int len) {

    typedef struct _Range {
        int start, end;
    } Range;

    Range new_Range(int s, int e) {
        Range r;
        r.start = s;
        r.end = e;
        return r;
    }

    if (len <= 0)
        return;

    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        char* mid = arr[range.end], * cp;
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (GTR(mid, arr[left]) && left < right)
                left++;
            while (!GTR(mid, arr[right]) && left < right)
                right--;
            cp = arr[left], arr[left] = arr[right], arr[right] = cp;
        }
        if (!GTR(mid, arr[left]))
            cp = arr[left], arr[left] = arr[range.end], arr[range.end] = cp;
        else
            left++;
        r[p++] = new_Range(range.start, left - 1);
        r[p++] = new_Range(left + 1, range.end);
    }
}

int GTR(char* s1, char* s2) {

    char * p1 = s1, * p2 = s2;

    while (1) {

        if (!*p1 && !*p2) return 1;

        if (!*p1) p1 = s2;

        if (!*p2) p2 = s1;

        if (*p1 > *p2)
            return 1;
        else if (*p1 < *p2)
            return 0;
        else p1++, p2++;

    }
}

char* largestNumber(int* nums, int numsSize) {

    char strs [numsSize][11], * strPtrs[numsSize], * cp1, * cp2, * strRet = malloc(10 * numsSize + 1), ch;

    int i, j, k, t;

    for (i = 0; i < numsSize; i++) {

        t = *(nums + i);
        j = 0;
        k = -1;

        // digits convert to string
        do {
            strs[i][j++] = '0' + t % 10;
        } while ((t /= 10) > 0);
        strs[i][j] = '\0';

        // reverse string
        *(strPtrs + i) = cp1 = *(strs + i);
        while (--j > ++k)
            * (cp1 + j) ^= *(cp1 + k), * (cp1 + k) ^= *(cp1 + j), * (cp1 + j) ^= *(cp1 + k);

    }

    q_sort(strPtrs, numsSize);

    // printf("After q_sort\n");
    // for (i = numsSize - 1; i >= 0; i--) printf("%s\n", strPtrs[i]);

    cp2 = strRet;

    if (strPtrs[numsSize - 1][0] == '0') {
        *strRet = '0';
        *(strRet + 1) = '\0';
        return strRet;
    }

    for (i = numsSize - 1; i >= 0; i--) {

        cp1 = *(strPtrs + i);
        while (ch = *(cp1++)) *(cp2++) = ch;

    }
    *cp2 = '\0';

    return strRet;
}
复制代码

1、用结构体 struct_num 保存数字和进位，排序时用 (long long) 数值比较大小，等到输出时再转为字符串
2、分设 10 个数组 hash 表，用于保存由 0-9 开头的数字组成的数组，这样只需要对 1-9 各组单独排序即可
3、函数自实现/内联，就题解题，节省函数调用开销
复制代码

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    

nums = nums.map(function(num) {
  return '' + num;
});
    

    var rs=[],re=[],p=0;
    rs[p] = 0;
    re[p++]= nums.length-1;

    var ss,ee,t;
    while (p) {

        ss = rs[--p];
        ee = re[p];

        if (ss >= ee)
            continue;

        var mid = nums[ee];

        var left = ss, right = ee - 1;
        while (left < right) {
            while (nums[left] + mid > mid + nums[left] && left < right)
                left++;
            while (mid + nums[right] >= nums[right] + mid && left < right)
                right--;
            t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
        }
        if (mid + nums[left] >= nums[left] + mid) {
            t = nums[left];
            nums[left] = nums[ee];
            nums[ee] = t;
        } else
            left++;

        rs[p] = ss;
        re[p++] = left - 1;

        rs[p] = left + 1;
        re[p++] = ee;

    }
    if (nums[0] == 0) return '0';
    return nums.join('');
};
复制代码

char outStr[];
int CompNums(const void* a, const void* b){
	char* str1=*(char**)a;
	char* str2=*(char**)b;
	int i, L1=strlen(str1), L2=strlen(str2);
	for(i=0; i<10; i++){
		if(*str1=='\0'){str1-=L1;}
		if(*str2=='\0'){str2-=L2;}
		if(*str1 != *str2){break;}
		str1++, str2++;
	}
	return *str2-*str1;
}
char* largestNumber(int* nums, int numsSize) {
	int i;
	outStr[0]=0;
	char* p[numsSize];
	for(i=0; i<numsSize; i++){p[i]=(char*)malloc(sizeof(char)*16);sprintf(p[i], "%d\0", nums[i]);}	
	qsort(p, numsSize, sizeof(char*), CompNums);
	for(i=0; i<numsSize; i++){strcat(outStr, p[i]);}
	return outStr[0]=='0'?"0":outStr;
}
复制代码

var largestNumber = function(nums) {
    return nums
        .sort((a,b) => ''+b+a > ''+a+b ? 1 : -1)
        .join('')
        .replace(/^0+(?=.)/,'')
}
复制代码

var largestNumber = function(nums) {
    let arr = [];
    for(let a of nums)arr.unshift(`${a}`)
    let retArr = arr.sort((a,b) => b+a > a+b ? 1 : -1)
    return retArr[0]==='0' ? '0' : retArr.join('')
}
复制代码

#!perl

my @n = ( 3, 30, 34, 5, 9 );
print sort { $b . $a cmp $a . $b } @n;
复制代码

class Solution:
    
    def largestNumber(self,nums): 
        l = len(str(max(nums)))+1
        new = [((str(i)*l)[:l],str(i)) for i in nums]
        new.sort(reverse = True) 
        res = "".join([i[1] for i in new])
        return "0" if res[0]=="0" else res
复制代码

// 2018-09-29

# include <stdio.h>
# include <stdlib.h>

typedef long long i64;
typedef struct { int tail; int val; } Num;

void sort(int*, int*, int);
int cmp(const void*, const void*);

int main (){
    int test[] = { 3, 30, 34, 5, 9 };
    int len    = sizeof(test) / sizeof(*test);
    int sorted[len];

    sort (test, sorted, len);
    for (int i = 0; i < len; i++)
        printf ("%d ", sorted[i]);
    
}

# define join(A, B) (A->val * (i64)B->tail + B->val)
int cmp(const void* A, const void* B){
    Num* a = (Num*) A;
    Num* b = (Num*) B;
    i64 ab = join (a, b);
    i64 ba = join (b, a);
    if (ab == ba) return 0;
    return ab > ba ? -1 : 1;
}

void sort(int* test, int* sorted, int len){
    Num n[len];

    for (int i = 0; i < len; i++){
        int tail = 1;
        int val  = test[i];

        while (val) tail *= 10, val /= 10;
        
        n[i].tail = tail;
        n[i].val  = test[i];
    }

    qsort(n, len, sizeof(Num), cmp);
    for (int i = 0; i < len; i++) sorted[i] = n[i].val;
}
    
复制代码