[挑战题]Largest Number

523066680

这里有一个算法竞赛网站出的题目 https://leetcode.com/problems/largest-number/

你可以选自己擅长的语言做题并上传代码，该网站会用各种极端情况的输入值测试你的代码，如果没有出错，则同其他人上传的代码效率做比较、排名

问题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.

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类型的整数（尤其是对于那些强类型的语言）
复制代码

可惜可以在该网站上传测试的语言类型有限，C/C++, java, python, ruby, js, go

523066680

本人上一次用C挑战的结果。测试221种输入情况累计用时 4ms-6ms




某群里最快的是0ms-2ms区间，C语言 （据说用语法糖越多的语言用时越多

523066680

回复 3# CrLf


    更快的当然是把那些sort函数之类的自己用更底层的语言实现啦。
好消息是我之前编译能过的代码现在不仅测试不通过而且本地编译运行崩溃，哈哈哈哈

523066680

回复 7# xxpinqz


    当输入数字是 830 8308 时，显示结果为：8308

523066680

大家都习惯花括号不换行吗……

523066680

#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;
}
复制代码

523066680

回复 17# GNU


      他们当然知道如何获取更详细的时间单位，说的是那个网站的在线测试的时间单位精度有限。
再说线下比较还可以增加测试次数和列表数据量。所以不同的结论需要结合前后文(Context)。

523066680

回复 19# happy886rr


    ? 贴了一个别人的，好像是快速排序

523066680

回复 25# xxpinqz

个人意见：
    多学几种语言，批处理之后，推荐ruby 或者 python，最好先熟悉C语言。
然后如果要自己打造应用，C# 或者 C++

刚工作那会儿有大量时间，我很后悔在批处理特效上面花太多时间，我不是说特效没卵用，而是搞图形的话应该一开始就上C/C++，可惜，当时缺少视野。
然后花了小量时间学Python，放弃后转而投入大量业余时间学Perl，这是手感上和批处理最像的。不过我觉得时间成本不太划算，C#、C++可以做更多的事。

最后，关于语言的吐槽，推荐一本书：《程序员的呐喊》