[剑指 Offer 第 2 版第 45 题] “把数组排成最小的数”做题记录

第 45 题：把数组排成最小的数

传送门：把数组排成最小的数，牛客网 online judge 地址。

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组 [3, 32, 321]，则打印出这 3 个数字能排成的最小数字 321323。

样例：

输入：[3, 32, 321]

输出：321323

注意：输出数字的格式为字符串。

同 LeetCode 第 179 题，最大数。

Java 代码：

  import java.util.Arrays;

    public class Solution {

        public String PrintMinNumber(int[] numbers) {
            int len = numbers.length;
            if (len == 0) {
                return "";
            }
            String[] numsStr = new String[len];
            for (int i = 0; i < len; i++) {
                numsStr[i] = numbers[i] + "";
            }
            Arrays.sort(numsStr, (a, b) -> (a + b).compareTo(b + a));
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < len; i++) {
                builder.append(numsStr[i]);
            }
            return builder.toString();
        }

        public static void main(String[] args) {
            int[] nums = new int[]{3, 32, 321};
            Solution solution = new Solution();
            String printMinNumber = solution.PrintMinNumber(nums);
            System.out.println(printMinNumber);
        }
    }

说明：其实就定义自定义排序规则。Python3 想用 cmp 而不是 key 的话，需要 from functools import cmp_to_key ，然后 sort 或者 sorted 的时候 key = cmp_to_key(your_comparator) 。

Python 代码：

  class Solution(object):
        def printMinNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: str
            """

            if len(nums) == 0:
                return ''
            # 自定义排序规则
            from functools import cmp_to_key
            key_func = cmp_to_key(lambda a, b: int(a + b) - int(b + a))
            result = sorted(map(str, nums), key=key_func)
            return ''.join(result)


    if __name__ == '__main__':
        list1 = [7, -8, 5, 4, 0, -2, -5]
        # 要求：1、正数在前负数在后
        # 2、正数从小到大
        # 3、负数从大到小

        result = sorted(list1, key=lambda x: (x < 0, abs(x)))
        print(result)

        s = 'asdf234GDSdsf23'  # 排序:小写-大写-奇数-偶数

        print(
            "".join(
                sorted(
                    s,
                    key=lambda x: (
                        x.isdigit(),
                        x.isdigit() and int(x) %
                        2 == 0,
                        x.isupper(),
                        x))))

另一种写法：

Python 代码：

  class NumCompare(str):
        # 注意：这里继承 str 类
        def __lt__(self, other):
            return self + other < other + self


    class Solution(object):
        def printMinNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: str
            """

            if len(nums) == 0:
                return ''
            # 自定义排序规则
            result = sorted(map(str, nums), key=NumCompare)
            return ''.join(result)

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/