Question source

题目描述

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

1. 解题思路：暴力

假设n个整数的索引为[0...n-1]，如果我们对这n个索引进行全排列，然后再对每次全排列进行组织一下结果，选取最小的即为答案。

Complexity

  • 时间复杂度：O(N*N!),全排列的时间复杂度为N！，每次排列结果需要遍历一次nums数组
  • 空间复杂度：O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void perm(int pos, vector<int> &num, string &ret) {
        if (pos + 1 == num.size()) {
            // 一次全排列的结果
            string tmp = "";
            for (int val : num) {
                tmp += to_string(val);
            }
            ret = min(ret, tmp);
            return;
        }
        for (int i = pos; i < num.size(); ++i) {
            swap(num[pos], num[i]);
            perm(pos+1, num, ret);
            swap(num[pos], num[i]);
        }
    }
    string PrintMinNumber(vector<int> nums) {
        string ret(nums.size(), '9'); // nums.size()个'9'
        perm(0, nums, ret);
        return ret;
    }
};

2. 解题思路：贪心，排序剪枝

显然方法一出现了太多无关的排列，我们需要一个最小的数，细想一下可知，如果有两个字符串a,b，如果a + b < b + a, 显然我们希望a排在b的前面，因为a排在前面可以使结果更小。于是我们就自定义排序规则，使得 numbers 中字符串都满足如上规则，那么，最后的字符串数组中字符串拼接的数字肯定是最小的。

算法步骤：

  1. numbers 转化为 numbers ；

  2. 自定义上述排序规则；

  3. 整合结果

Complexity

  • 时间复杂度：O(NlogN), 采用了排序
  • 空间复杂度：O(N)

Code

1
2
3
4
5
6
7
8
9
# -*- coding:utf-8 -*-
class Solution: 
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers: return ''
        numbers = list(map(str,numbers))
        numbers.sort(cmp=lambda x,y:cmp(x + y, y + x))
        return ''.join(numbers).lstrip('0') or '0'

⚠️

1
2
3
4
5
6
7
# Python lstrip() 方法用于截掉字符串左边的空格或指定字符。
str.lstrip([chars]) # chars --指定截取的字符。

# cmp(x,y) 函数用于比较2个对象，如果 x < y 返回 -1, 如果 x == y 返回 0, 如果 x > y 返回 1。
# 以上实例运行后输出结果为：    
cmp(80, 100) :  -1
cmp(180, 100) :  1

参考