给定一个长度为n的数组nums,数组由一些非负整数组成,现需要将他们进行排列并拼接,每个数不可拆分,使得最后的结果最大,返回值需要是string类型,否则可能会溢出。
数据范围:
,
进阶:时间复杂度
,空间复杂度:)
[30,1]
"301"
[2,20,23,4,8]
"8423220"
[2]
"2"
[10]
"10"
输出结果可能非常大,所以你需要返回一个字符串而不是整数。
把数字转为字符串,然后strncmp进行比较,结合比较结果和不同情况,进行不同状态的特殊处理
本地仿真都正常,但就是结果结果不对
/**
* 最大数
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return string字符串
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
static char str_ret[501] = {'\0'};
void swap(char *str1, char *str2)
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
char tmp[6] = {'\0'};
strcpy(tmp,str1);
strcpy(str1,str2);
strcpy(str2,tmp);
str1[str2_len] = '\0';
str2[str1_len] = '\0';
}
int numtostring(int num, char *str)
{
int str_index = 0;
int multiple[4] = {0, 1,10,100,1000,10000};
int tmp = 0;
int bit = 0;
for(int i = 5; i > 0; i--)
{
bit = tmp / multiple[i];
if((bit) || (str_index)) //高位0->不转换 高位非0及低位非0需要填充
{
str[str_index] = bit + '0' - 0;
str_index++;
}
tmp = num % multiple[i]; //xxxxx
}
return str_index;
}
char* solve(int* nums, int numsLen ) {
// write code here
char str[100][6] = {'\0'};
int str_ret_len = 0;
int strlen1 = 0;
int strlen2 = 0;
int min_strlen = 0;
int cmp_ret = 0;
//char tmp[6] = {'\0'};
for(int i = 0; i < numsLen; i++)
{
numtostring(nums[i], &str[i][0]);
}
for(int i = 0; i < numsLen; i++)
{
for(int j = i + 1; j < numsLen; j++)
{
strlen1 = strlen(&str[i][0]);
strlen2 = strlen(&str[j][0]);/*
if((str[j][strlen2 - 1] == '0') && (str[i][strlen1 - 1] != '0'))
{
str[j][strlen2 - 1] = '\0';
if(strcmp(&str[j][0],&str[i][0]) > 0)
swap(&str[j][0],&str[i][0]);
str[i][strlen2 - 1] = '0'; //恢复现场
str[i][strlen2] = '\0';
}
else if((str[j][strlen2 - 1] != '0') && (str[i][strlen1 - 1] == '0'))
{
str[i][strlen1 - 1] = '\0';
if(strcmp(&str[j][0],&str[i][0]) > 0)
swap(&str[j][0],&str[i][0]);
str[j][strlen1 - 1] = '0'; //恢复现场
str[j][strlen1] = '0';
}
else */
min_strlen = strlen1 > strlen2 ? strlen2 : strlen1;
cmp_ret = strncmp(&str[j][0],&str[i][0],min_strlen);
if(cmp_ret > 0)
{
swap(&str[j][0],&str[i][0]);
}
else if(cmp_ret == 0)
{
if(strlen1 > strlen2)
{
if(str[i][strlen2] < str[i][0])
{
swap(&str[j][0],&str[i][0]);
}
}
else if(strlen1 < strlen2)
{
if(str[i][0] < str[j][strlen1]) //比如str[i] = 2; str[j] = 23,需要进行替换,232
{
swap(&str[j][0],&str[i][0]);
}
}
}
}
}
for(int i = 0; i < numsLen; i++)
{
strcpy(&str_ret[str_ret_len],&str[i][0]);
str_ret_len += strlen(str[i]);
}
str_ret[str_ret_len] = '\0';
printf("%s\n",str_ret);
return str_ret;
}