当前位置:首页 > 芯闻号 > 充电吧
[导读]问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32,  321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。

问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32,  321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。

      思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba。如果ab < ba,则a < b;如果ab > ba,则a > b;如果ab = ba,则a = b。比较函数的定义是本解决方案的关键。这道题其实就是希望我们能找到一个排序规则,根据这个规则排出来的数组能排成一个最小的数字。

      证明:为什么这样排个序就可以了呢?简单证明一下。根据算法,如果a < b,那么a排在b前面,否则b排在a前面。可利用反证法,假设排成的最小数字为xxxxxx,并且至少存在一对字符串满足这个关系:a > b,但是在组成的数字中a排在b前面。根据a和b出现的位置,分三种情况考虑:

      (1)xxxxab,用ba代替ab可以得到xxxxba,这个数字是小于xxxxab,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。

      (2)abxxxx,用ba代替ab可以得到baxxxx,这个数字是小于abxxxx,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。

      (3)axxxxb,这一步证明麻烦了一点。可以将中间部分看成一个整体ayb,则有ay < ya,yb < by成立。将ay和by表示成10进制数字形式,则有下述关系式,这里a,y,b的位数分别为n,m,k。

        关系1: ay < ya => a * 10^m + y < y * 10^n + a => a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y

        关系2: yb < by => y * 10^k + b < b * 10^m + y => y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1) 

        关系3: a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  => a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b

       这与假设a > b矛盾。因此排成的最小数字中,不存在上述假设的关系。

       综上所述,得出假设不成立,从而得出结论:对于排成的最小数字,不存在满足下述关系的一对字符串:a > b,但是在组成的数字中a出现在b的前面。从而得出算法是正确的。

代码一:利用指针。

#include 
#include 
using namespace std;

const int g_MaxNumberLength=10;
char* g_StrCombine1=new char[g_MaxNumberLength*2+1];
char* g_StrCombine2=new char[g_MaxNumberLength*2+1];

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**)(new int[length]);
	for(int i=0; i>Num;
	int *numbers=new int[Num];
	for(int i=0; i>numbers[i];

	PrintMinNumber(numbers, Num);
}


代码二:利用string类。

#include 
#include 
#include 
#include 
using namespace std;

bool compare(const string& str1, const string &str2)
{
	string s1=str1+str2;
	string s2=str2+str1;
	return s1>pStrArray[i];		
	}

	sort(pStrArray, pStrArray+num, compare);

	for(i=0; i>Num;
	int *pArray=new int[Num];

	for(int i=0; i>pArray[i];

	ComArrayMin(pArray, Num);

}

感谢:http://blog.csdn.net/wuzhekai1985/article/details/6704902

           http://blog.csdn.net/xianliti/article/details/5649876
 

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

业内消息,苹果正在中国寻找本土生成式AI提供方,近日传与百度就在中国市场的苹果设备中使用百度的生成式人工智能技术进行了初步谈判,或将在中国市场的苹果设备提供本土AI大模型,因为中国法律要求大模型在被允许使用之前,必须得到...

关键字: 苹果 百度 AI

据报道,百度创始人李彦宏不止一次对外说过百度的AI很牛。去年文心一言出来后,李彦宏声称文心一言和ChatGPT的差距可能在一到两个月左右,差距不大。对此,原搜狗创始人,现百川智能创始人王小川近日在接受采访时犀利吐槽:李彦...

关键字: 王小川 百度 李彦宏 百川智能

业内消息,近日在央视播出的《对话》・开年说节目上,百度创始人、董事长兼首席执行官李彦宏表示,以后不会存在“程序员”这种职业了,因为只要会说话,所有人都能具备程序员的能力。李彦宏认为,未来的编程语言只会剩下两种,一种叫做英...

关键字: 百度 李彦宏 程序员 AI

2月29日消息,在百度2023年第四季度及全年财报电话会上,百度创始人、董事长兼首席执行官李彦宏透露,百度文心大模型推理成本已降至1%。

关键字: 李彦宏 百度

业内消息,近日有媒体报道称,百度计划将量子实验室及设备捐赠给北京量子信息科学研究院,双方正商讨具体细节。此前,阿里达摩院宣布已将量子实验室及可移交的量子实验仪器设备捐赠予浙江大学,并向其他高校和科研机构进行开放。

关键字: 百度 量子实验室 北京量子院

1月1日,港交所公告显示,百度关联方MoonSPV Limited按照此前签署的协议行使合同权利,终止此前与百度与欢聚集团联合签署对YY Live的股权收购协议。Moon表示会就终止股权收购协议后交易未来安排寻求与欢聚集...

关键字: 百度 Moon YY 直播

11月20日消息,OpenAI的内斗大戏又有了进展,根据国外媒体最新报道,OpenAI 想把刚刚被他们驱逐的前CEO山姆·奥特曼(Sam Altman)给重新请回去。

关键字: ChatGPT AI 百度 文言一心

10月9日消息,目前,国内有多家科技大厂陆续发布自家大模型,被业内看作为AI大模型百“模”大战已经打响。

关键字: 文心大模型 百度 人工智能

业内消息,近日百度发布了首个量子领域大模型,并推出了量子写作助手等一系列量子应用产品。与此同时,阿里云宣布开源通义千问 14B 模型及其对话模型 Qwen-14B-Chat,并且免费可商用。

关键字: 百度 量子大模型 阿里云 通义千问

业内消息,近日百度宣布旗下知识增强大语言模型文心一言首批获批将向全社会开放,官方表示广大用户可以在应用商店下载文心一言App 或登陆文心一言官网(https://yiyan.baidu.com)体验。

关键字: 百度 文心一言 大语言模型
关闭
关闭