输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。
分析:这是09年6月份百度新鲜出炉的一道面试题,从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
这道题其实是希望我们能找到一个排序规则,根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则,就得比较两个数字,也就是给出两个数字m和n,我们需要确定一个规则m和n哪个更大,而不是仅仅只是比较这两个数字的数值哪个更大。
根据题目的要求,两个数字m和n排成的数字mn和nm,如果mn<nm,那么我们应该输出mn,也就是m应该排在n的前面,也就是m小于n;反之,如果nm<mn,n小于m。如果mn==mn,m等于n。
接下来我们考虑怎么去拼接数字,即给出数字m和n,怎么得到数字mn和nm并比较它们的大小。直接用数值去计算不难办到,但需要考虑到的一个潜在问题是m和n都在int能表达的范围内,但把它们拼起来的数字mn和nm就不一定能用int表示了。所以我们需要解决大数问题。一个非常直观的方法就是把数字转换成字符串。
另外,由于把数字m和n拼接起来得到的mn和nm,它们所含有的数字的个数肯定是相同的。因此比较它们的大小只需要按照字符串大小的比较规则就可以了。
基于这个思路,我们可以写出下面的代码:
// Maxinum int number has 10 digits in decimalsystem
const intg_MaxNumberLength = 10;
// String buffers to combine two numbers
char*g_StrCombine1 =
new char[g_MaxNumberLength * 2 + 1];
char*g_StrCombine2 =
new char[g_MaxNumberLength * 2 + 1];
// Given an array, print the minimum number
// by combining all numbers in the array
voidPrintMinNumber(int* numbers,
int length)
{
if(numbers== NULL || length <= 0)
return;
// Convert all numbers as strings
char**strNumbers = (char**)(new
int[length]);
for(int i = 0; i < length;++i)
{
strNumbers[i] = new
char[g_MaxNumberLength +1];
sprintf(strNumbers[i], "%d",numbers[i]);
}
// Sort all strings according to algorithm infunction compare
qsort(strNumbers, length, sizeof(char*), compare);
for(int i = 0; i < length;++i)
printf("%s",strNumbers[i]);
printf("\n");
for(int i = 0; i < length;++i)
delete[] strNumbers[i];
delete[] strNumbers;
}
// Compare two numbers in strNumber1 andstrNumber2
// if [strNumber1][strNumber2] >[strNumber2][strNumber1],
// return value > 0
// if [strNumber1][strNumber2] =[strNumber2][strNumber1],
// return value = 0
// if [strNumber1][strNumber2] <[strNumber2][strNumber1],
// return value < 0
intcompare(const
void* strNumber1,
const void* strNumber2)
{
// [strNumber1][strNumber2]
strcpy(g_StrCombine1, *(const
char**)strNumber1);
strcat(g_StrCombine1, *(const
char**)strNumber2);
// [strNumber2][strNumber1]
strcpy(g_StrCombine2, *(const
char**)strNumber2);
strcat(g_StrCombine2, *(const
char**)strNumber1);
return strcmp(g_StrCombine1, g_StrCombine2);
}
上述代码中,我们在函数compare中定义比较规则,并根据该规则用库函数qsort排序。最后把排好序的数组输出,就得到了根据数组排成的最小的数字。
找到一个算法解决这个问题,不是一件容易的事情。但更困难的是我们需要证明这个算法是正确的。接下来我们来试着证明。
首先我们需要证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较需要三个条件:1.自反性,即a等于a;2.对称性,即如果a大于b,则b小于a;3.传递性,即如果a小于b,b小于c,则a小于c。现在分别予以证明。
自反性。显然有aa=aa,所以a=a。
对称性。如果a小于b,则ab<ba,所以ba>ab。因此b大于a。
传递性。如果a小于b,则ab<ba。当a和b用十进制表示的时候分别为l位和m位时,ab=a×10m+b,ba=b×10l+a。所以a×10m+b<b×10l+a。于是有a×10m-a<
b×10l –b,即a(10m-1)<b(10l -1)。所以a/(10l
-1)<b/(10m -1)。
如果b小于c,则bc<cb。当c表示成十进制时为m位。和前面证明过程一样,可以得到b/(10m-1)<c/(10n
-1)。
所以a/(10l-1)< c/(10n -1)。于是a(10n -1)<c(10l
-1),所以a×10n +c<c×10l +a,即ac<ca。
所以a小于c。
在证明了我们排序规则的有效性之后,我们接着证明算法的正确性。我们用反证法来证明。
我们把n个数按照前面的排序规则排好顺序之后,表示为A1A2A3…An。我们假设这样排出来的两个数并不是最小的。即至少存在两个x和y(0<x<y<n),交换第x个数和地y个数后,A1A2…Ay…Ax…An<A1A2…Ax…Ay…An。
由于A1A2…Ax…Ay…An是按照前面的规则排好的序列,所以有Ax<Ax+1<Ax+2<…<Ay-2<Ay-1<Ay。
由于Ay-1小于Ay,所以Ay-1Ay<AyAy-1。我们在序列A1A2…Ax…Ay-1Ay…An交换Ay-1和Ay,有A1A2…Ax…Ay-1Ay…An<A1A2…Ax…AyAy-1…An(这个实际上也需要证明。感兴趣的读者可以自己试着证明)。我们就这样一直把Ay和前面的数字交换,直到和Ax交换为止。于是就有A1A2…Ax…Ay-1Ay…An<A1A2…Ax…AyAy-1…An<
A1A2…Ax…AyAy-2Ay-1…An<…<A1A2…AyAx…Ay-2Ay-1…An。
同理由于Ax小于Ax+1,所以AxAx+1<Ax+1Ax。我们在序列A1A2…AyAxAx+1…Ay-2Ay-1…An仅仅只交换Ax和Ax+1,有A1A2…AyAxAx+1…Ay-2Ay-1…An<A1A2…AyAx+1Ax…Ay-2Ay-1…An。我们接下来一直拿Ax和它后面的数字交换,直到和Ay-1交换为止。于是就有A1A2…AyAxAx+1…Ay-2Ay-1…An<A1A2…AyAx+1Ax…Ay-2Ay-1…An<…<A1A2…AyAx+1Ax+2…Ay-2Ay-1Ax…An。
所以A1A2…Ax…Ay…An<A1A2…Ay…Ax…An。这和我们的假设的A1A2…Ay…Ax…An
<A1A2…Ax…Ay…An相矛盾。
所以假设不成立,我们的算法是正确的。
分享到:
相关推荐
把数组排成最小的数.md
java基础面试题把数组排成最小的数
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解法一:cmp_to_key函数 from ...
剑指 Offer 45. 把数组排成最小的数解法二个数字a,b拼成数字ab,如果ab ,则应该打印ab,否则打印ba。
题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的
示例 1:输入: [10,2]输出: "102"示例 2:输入: [3,30,34,5,9]输出: "3033459"bool mycmp(string& x,
剑指Offer(Python多种思路实现):把数组排成最小的数 面试45题: 题:把数组排成最小的数 题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
把数组排成最小的数 解法:自定义排序规则(Python) 详细参考 Krahets class Solution: def minNumber(self, nums: List[int]) -> str: def sort_rule(x, y): a, b = x + y, y + x if a > b: return 1 elif a...
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 输出结果可能非常大,所以需要返回一个字符串而不是整数。 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导...
问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。 思路:先将...
26.树的子结构 Tree 常考 27.二叉树的镜像 Tree 28.对称的二叉树 Tree 29.顺时针打印矩阵 Array 30.包含min函数的栈 Stack ...45.把数组排成最小的数 String 46.把数字翻译成字符串 String 47.礼物的
最近在工作碰到一个问题,就是用javascript求数组中所有数字能拼接出的最大整数,数组的每一项为单独的拼接项,不能再拆开,例如[2,34]中2和34分别为要被拼接的数字,而不是说34还能继续拆分为3和4。 具体需求为,...
用数组实现约瑟夫出圈问题。 n个人排成一圈,从第一个人开始报数,从1开始报,报到m的人出圈,剩下的人继续开始从1报数,直到所有的人都出圈为止。对于给定的n,m,编写程序求出所有人的出圈顺序。
把数组排成最小的数 存在重复元素 打乱数组 三数之和 化栈为队 144.二叉树的前序遍历 146.LRU缓存机制 155.最小栈 31.栈的压入、弹出序列 32.从上到下打印二叉树 有效的括号 面试题59 - I. 滑动窗口的最大值 71.简化...
按之字形顺序打印二叉树,把二叉树打印成多行,把数组排成最小的数,把字符串转化成整数,包含min函数的栈,变态青蛙跳,表示数值的字符串,不用加减乘除做加法,丑数,从上往下打印二叉树,从尾到头打印链表,第一个只出现一次...
利用数组的报数出队程序,不同于简单的链表报数!!
简单来讲,多维数组就是“数字的集合”,数字排成一列的集合、排成长方形的集合、排成三维状或者(更加一般化)N 维状的集合都称为多维数组。 如上所述,数组的维数可以通过 np.dim()函数获得。此外,数组的形状...
把数组排成最小的数 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 先将整型数组转换成...