题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{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,它们所含有的数字的个数肯定是相同的。因此比较它们的大小只需要按照字符串大小的比较规则就可以了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int g_MaxNumberLength=10;
char* g_StrCombine1=(char*)malloc((2*g_MaxNumberLength+1)*sizeof(char));
char* g_StrCombine2=(char*)malloc((2*g_MaxNumberLength+1)*sizeof(char));
//定义比较规则
int compare(const void* strNumber1,const void* strNumber2)
{
strcpy(g_StrCombine1,*(const char**)strNumber1);
strcat(g_StrCombine1,*(const char**)strNumber2);
strcpy(g_StrCombine2,*(const char**)strNumber2);
strcat(g_StrCombine2,*(const char**)strNumber1);
return strcmp(g_StrCombine1,g_StrCombine2);
}
void printMinNumber(int* numbers,int length)
{
if(numbers==NULL||length<=0)
return;
char** strNumbers=(char**)malloc(length*sizeof(int));
for(int i=0;i<length;++i)
{
strNumbers[i]=(char*)malloc((g_MaxNumberLength+1)*sizeof(char));
sprintf(strNumbers[i],"%d",numbers[i]);
}
qsort(strNumbers,length,sizeof(char*),compare);//库函数qsort排序
for(int i=0;i<length;++i)
printf("%s",strNumbers[i]);
printf("\n");
for(int i=0;i<length;i++)
free(strNumbers[i]);
free(strNumbers);
}
int main()
{
int* numbers;
int length;
scanf("%d",&length);
numbers=(int*)malloc(length*sizeof(int));
for(int i =0;i<length;i++)
scanf("%d",&numbers[i]);
printMinNumber(numbers,length);
return 0;
}
结果:
分享到:
相关推荐
【免费题库】华为OD机试 - 数组组成的最小数字(Java & JS & Python & C & C++).html
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解法一:cmp_to_key函数 from ...
指针 ~~编写一个函数,将数组中n个数按反序存放。 实验步骤与要求: 在主函数中输入10个数,并输出排好序的数。 编写函数invert()将10个数按反序存放。
主要介绍了Java 实现查找旋转数组的最小数字,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
从n个数组中取出所有排列组合(Java实现)
labview随机数生成并组成数组.vi
桂林电子科技大学计算机与信息安全学院计算机组成原理课程设计,题目为输入包含10个整数(无符号数)的数组M,输出中位数。文件里面有代码,有文档。下载可直接使用。
组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种...
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...
计算由2个相同大小N的自然数的升序数组组成的数组的中位数。不检查数组的正确排序。 局限性: 每个序列中最大的数字N为1073741823(具有足够的内存)。 序列中数字的最大允许值为9223372036854775807。 解决问题...
p为指向整型二维数组的指针变量,二维数组的列数为n int *p() p为返回指针值的函数,该指针指向整型量 int (*p)() p为指向函数的指针,该函数返回整型量 int **p p为一个指向另一指针的指针变量,该指针指向一个...
自己做的一个简单的求一组数据中两个最大的数和两个最小的数,并且求数组的和,然后输出!
实现一个“可变长二维数组”,这个二维数组的行数可由输入决定,每行的元素个数仍可由输入决定。每个数组元素值都是1. 执行结果如下: 请输入行数: 5 请输入第1行的元素个数: 20 请输入第2行的元素个数: 34 请...
一维数组转二维数组
在前面板窗口控件选板中选择控件“新式→数组、矩阵与簇→数组,置于前面板窗口的空白处,如图1所示。 数组框架由左侧的索引号和右侧的元素区域两部分组成,如图2所示。通过索引可以直接定位到数组的行、列,行列...
HashMap用桶的话会有一个问题,加入这个数组的取值范围是0~9999,数组的组成是{1,2,9998,2,1},我们为了把5个数中间单独出现的那一个数取出来
给定n 个整数组成的序列,现在要求将序列分割为m 段,每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小? 编程任务: 给定n 个整数组成的序列,编程计算该序列的最优m 段分割,...
此示例数组由10 个数组元素组成,每个数组元素都有一个相应的索引号,用于指定数组元素在数组中的位置。第一个数组元素的索引为 0。第二个数组元素的索引为 1。第三个数组元素的索引为 2 依此类推。索引6的数组元素...
连续数字组成一个数组提取.md
数组是由相同类型的元素组成的一组数据。在 MATLAB 中,可以使用一维数组和多维数组。一维数组也称为向量,多维数组也称为矩阵。数组的元素可以是数字、字符、逻辑值或对象等。 矩阵是一种特殊的二维数组,其中每个...