1. 题目
把数组排成最小的数
输入一个非负整数数组 numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如,输入数组 [3,32,321]
,则打印出这三个数字能排成的最小数字为 321323。
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数;
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0。
数据范围:
0<=len (numbers)<=100
示例 1
输入[11,3]
输出
"113"
说明:文中的解题思路及程序来源于《剑指 Offer——名企面试官精讲典型编程题》书中面试题 45,如有兴趣可以找到这本书来阅读。
2. 解题思路
这个题目最直接的做法应该是先求出这个数组中所有数字的全排列,然后把每个排列拼起来,最后求出拼起来的数字的最小值。根据排列组合的知识,n 个数字总共有 n! 个排列。我们再来看一种更快的算法。
这道题其实是希望我们能找到一个排序规则,数组根据这个规则排序之后能排成一个最小的数字。要确定排序规则,就要比较两个数字,也就是给出两个数字 m 和 n,我们需要确定一个规则判断 m 和 n 哪个应该排在前面,而不是仅仅比较这两个数字的值哪个更大。
根据题目的要求,两个数字 m 和 n 能拼接成数字 mn 和 nm。如果 mn<nm,那么我们应该打印出 mn,也就是 m 应该排在 n 的前面,我们定义此时 m 小于 n;
反之,如果 nm<mn,我们定义 n 小于 m。如果 mn=nm,m 等于 n。在下文中,符号"<"、">"及"="表示常规意义的数值的大小关系,而文字"大于"、"小于"、"等于"表示我们新定义的大小关系。
接下来考虑怎么去拼接数字,即给出数字 m 和 n,怎么得到数字 mn 和 nm 并比较它们的大小。直接用数值去计算不难办到,但需要考虑到一个潜在的问题就是 m 和 n 都在 int 能表达的范围内,但把它们拼起来的数字 mn 和 nm 用 int 表示就有可能溢出了,所以这还是一个隐形的大数问题。一个非常直观的解决大数问题的方法就是把数字转换成字符串。
另外,由于把数字 m 和 n 拼接起来得到 mn 和 nm,它们的位数肯定是相同的,因此比较它们的大小只需要按照字符串大小的比较规则就可以了。
3. 示例代码
3.1 先全排列,再进行比较
以下代码是用 python 编写的全排列的解题代码:
from copy import deepcopy
# 全排列
def Permutation(strArray:list):
list_len = len(strArray)
if list_len <= 1: # 递归到最后一个元素,不能再递归了,直接返回
return strArray
res = []
for i in range(len(strArray)): # 固定一个元素
tempArray = deepcopy(strArray) # deepcopy:深拷贝
numStr = tempArray.pop(i)
result = Permutation(tempArray)
for j in result:
tmp = numStr + j
res.append(tmp)
return res
if __name__ == "__main__":
numArray = [4, 32, 21]
numStrArray = [str(x) for x in numArray] # ['4', '32', '21']
ret_val = Permutation(numStrArray)
print(f"ret_val: {ret_val}")
print(f"min(ret_val): {min(ret_val)}")
3.2 基于自定义的比较方法
示例代码:
/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.
Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/
//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者:何海涛
//==================================================================
// 面试题45:把数组排成最小的数
// 题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼
// 接出的所有数字中最小的一个。例如输入数组{3, 32, 321},则打印出这3个数
// 字能排成的最小数字321323。
#include <cstdio>
#include <cstring>
#include <algorithm>
int compare(const void *strNumber1, const void *strNumber2);
// int型整数用十进制表示最多只有10位
const int g_MaxNumberLength = 10;
char *g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];
char *g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];
void PrintMinNumber(const int *numbers, int length)
{
if (numbers == nullptr || length <= 0)
return;
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]);
}
// TODO: qsort在这里是如何对数据进行排序的?
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;
}
// 如果[strNumber1][strNumber2] > [strNumber2][strNumber1], 返回值大于0
// 如果[strNumber1][strNumber2] = [strNumber2][strNumber1], 返回值等于0
// 如果[strNumber1][strNumber2] < [strNumber2][strNumber1], 返回值小于0
int compare(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);
}
// ====================测试代码====================
void Test(const char *testName, int *numbers, int length, const char *expectedResult)
{
if (testName != nullptr)
printf("%s begins:\n", testName);
if (expectedResult != nullptr)
printf("Expected result is: \t%s\n", expectedResult);
printf("Actual result is: \t");
PrintMinNumber(numbers, length);
printf("\n");
}
void Test1()
{
int numbers[] = {6, 5, 1, 4, 2};
Test("Test1", numbers, sizeof(numbers) / sizeof(int), "12345");
}
void Test2()
{
int numbers[] = {3, 32, 321};
Test("Test2", numbers, sizeof(numbers) / sizeof(int), "321323");
}
void Test3()
{
int numbers[] = {3, 323, 32123};
Test("Test3", numbers, sizeof(numbers) / sizeof(int), "321233233");
}
void Test4()
{
int numbers[] = {1, 11, 111};
Test("Test4", numbers, sizeof(numbers) / sizeof(int), "111111");
}
// 数组中只有一个数字
void Test5()
{
int numbers[] = {321};
Test("Test5", numbers, sizeof(numbers) / sizeof(int), "321");
}
void Test6()
{
Test("Test6", nullptr, 0, "Don't print anything.");
}
int main(int argc, char *argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
return 0;
}
以上代码中的核心内容是 qsort
,即快速排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序的主要步骤:
4. 总结
在上述代码中,我们先把数组中的整数转换成字符串,在函数 compare
中定义比较规则,并根据该规则用库函数 qsort
排序。最后把排好序的数组中的数字依次打印出来,就是该数组中数字能拼接出来的最小数字。这种思路的时间复杂度和 qsort
的时间复杂度相同, 也就是 O(nlogn)
,这比用 n!
的时间求出所有排列的思路要好很多。
5. 其他参考
class Solution {
public:
//排序规则
static bool cmp(int a, int b)
{
string A = "";
string B = "";
A+=to_string(a);
A+=to_string(b);
B+=to_string(b);
B+=to_string(a);
return A<B;
}
string PrintMinNumber(vector<int> numbers) {
if(numbers.empty())
return "";
string ret = "";
sort(numbers.begin(),numbers.end(),cmp);
for(size_t i = 0; i < numbers.size(); ++i)
ret += to_string(numbers[i]);
return ret;
}
};
#include <iostream> // 包含头文件 iostream
#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
string minNumber(vector<int> &nums)
{
vector<string> nums_str(nums.size());
for (int i = 0; i < nums.size(); i++)
{
nums_str[i] = to_string(nums[i]);
}
QuickSort(nums_str, 0, nums.size() - 1);
string result;
for (string s : nums_str)
{
result += s;
}
return result;
}
static void QuickSort(vector<string> &strs, int l, int r)
{
if (l >= r)
return;
int i = l, j = r;
string tmp = strs[i];
while (i < j)
{
while ((strs[j] + strs[l]).compare(strs[l] + strs[j]) >= 0 && i < j)
j--;
while ((strs[i] + strs[l]).compare(strs[l] + strs[i]) <= 0 && i < j)
i++;
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[l];
strs[l] = tmp;
QuickSort(strs, l, i - 1);
QuickSort(strs, i + 1, r);
}
};
int main()
{
vector<int> nums{3, 30, 34, 5, 9};
Solution s;
string result = s.minNumber(nums);
cout << result << endl;
return 0
}