1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3291.html

« [剑指 Offer 第 2 版第 44 题] “数字序列中某一位的数字”做题记录
[剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录»

相关推荐

QR code