首页 编程学习

1. 题目

把数组排成最小的数
输入一个非负整数数组 numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如，输入数组 [3，32，321]，则打印出这三个数字能排成的最小数字为 321323。

  1. 输出结果可能非常大，所以你需要返回一个字符串而不是整数；
  2. 拼接起来的数字可能会有前导 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，即快速排序，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的主要步骤：

  1. 先从数列中取出一个数作为基准数。
  2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  3. 再对左右区间重复第二步，直到各区间只有一个数。排序的过程如下图所示：
    20161104203945998.gif

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
    
}
版权属于：jobyan
本文链接：http://codeupbetter.com/index.php/2023/11/13/146.html
作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
文章评论
目录