描述

题目描述

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

示例

输入：[3,32,321]
输出："321323"

题目要求求出拼接后数字最小，并且处理的对象是数组，那么我们应该想到比较以及排序

知识点：数字、字符串、排序
难度：三星

题解

解题思路

求最大最小的问题，往往能涉及到比较和排序问题。

题目要求拼接后的最小数字，其实就是一个排序问题。

对于数组 numbers，我们假设其中数组相对下标小的一个元素为 a，相对下标大的元素为 b，可以有以下几种情况：

  • a 和 b 拼接后的字符串 a + b > b + a， 那么不难想到 a 大于 b，所以要求最小数字，应该是 a 在 b 的右边元素
  • 相对的，a + b < b + a，则 a 小于 b，“小于” 指在数组中 a 应该在 b 的左边，保证数组拼接字符串后保证数字最小

难以理解的话，我们拿示例 [3,32,321] 举例子， a = 3，b = 32

  • a + b 字符串拼接后为：332，b + a 字符串拼接后为：323，即 a + b > b + a， 则 a 和 b，也就是 3 和 32 应该交换位置
  • 假如 a 为 3，b为 321，也同样应该交换位置，结果数组应该是：[321, 32, 3]

往往复杂的问题我们可以先以简单的例子来帮助理解

方法一：自定义排序规则

根据上面的题解思路，我们可以自定义排序规则（对于数组 numbers 中任意两个元素的字符串为 a 和 b）：

  • a + b > b + a， 则 a 大于 b

  • 相对的，a + b < b + a，则 a 小于 b

图解

image-20210622160708996

算法流程：
  • 对数组的左右两个元素通过两次相反顺序的拼接成字符串后，进行大小比较并排序
  • 前+后 > 后+前, 就交换位置 j 和 j+1, 保证数组顺序是从左到右从小到大
  • 经过 O (NlogN) 级别时间复杂度的比较排序后，结果转为字符串
Java 版本代码如下：
import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length <= 0) {
            return "";
        }
        int len = numbers.length;
        // 从numbers的左右两个元素进行大小比较并排序
        // 每次结果一个for循环后，保证下标为 len - 1 的元素顺序是正确的
        for(int i=0; i<len; i++){ for(int j="0;" j<len-i-1; j++){ string s1="numbers[j]" + "" numbers[j+1]; s2="numbers[j" 1] numbers[j]; 前+后> 后+前, 就交换位置j和j+1,保证数组顺序是从左到右从小到大
                if(s1.compareTo(s2) > 0){
                    swap(numbers, j);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0; i<len; i++){ sb.append(numbers[i]); } return sb.tostring(); 交换数组的左右两个元素 public void swap(int[] numbers, int j) { temp="numbers[j];" numbers[j]="numbers[j+1];" numbers[j+1]="temp;" ``` ###### python 版本代码如下： ```go class solution: def printminnumber(self, numbers): # write code here res="[]" 和上面的两层for循环相同用法 for i in range(len(numbers)-1): j range(i+1,len(numbers)): 每次比较都会选择数字最高位但最小的放前面 if str(numbers[i]) + str(numbers[j])> str(numbers[j]) + str(numbers[i]):
                    # 交换位置
                    numbers[i],numbers[j] = numbers[j],numbers[i]
        res = ''.join(str(i) for i in numbers)
        return res

复杂度分析：

时间复杂度：O(NlogN)，两个循环实现自定义排序
空间复杂度：O(N)， 用到了数组、StringBuilder 等需要开辟额外空间的类型用来存储结果

总结：有关数组的大小、最大、最小相关的问题，应该要联系到比较、排序，也有可能用到栈、队列等数据结构

方法二：贪心

既然整个序列是最小的，那么越靠前的元素肯定也是最小的，即越靠前的元素值越小

算法流程：
  • 转为字符串数组
  • 对每个相邻元素进行自定义排序，每次确定最前面或者最后面的元素
Java 版本代码如下：

直接使用内置排序方法

import java.util.ArrayList;

public class Solution {
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            str[i] = String.valueOf(nums[i]);
        }
        // 内置排序方法，若 x + y > y + x, 则表明 x “大于” y，sort默认升序排序，因此x 和 y 交换位置，实现排序
        Arrays.sort(str, (x, y) -> (x + y).compareTo(y + x));
        String res = "";
        for(String s : str) {
            res += s;
        }
        return res;
    }
}
Python 版本代码如下：
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            a, b = x + y, y + x
            if a > b: return 1
            elif a < b: return -1
            else: return 0

        strs = [str(num) for num in nums]
        strs.sort(key = functools.cmp_to_key(sort_rule))
        return ''.join(strs)

复杂度分析：

时间复杂度：O(NlogN)，用到了内置方法的排序，默认是用快排
空间复杂度：O(N)， 用到了字符串、数组

总结：有关数组的大小、最大、最小相关的问题有时候也用到贪心思想

</len;></len;>