2022年 11月 9日

剑指offer第二版(Python3)–面试题45 : 把数组排成最小的数

第2章 面试需要的基础知识

第3章 高质量的代码

第4章 解决面试题的思路

第5章 优化时间和空间效率

  面试题39 : 数组中出现次数超过一半的数字

  面试题40 : 最小的k个数

  面试题42 : 连续子数组的最大和

  面试题43 : 从1到n整数中1出现的次数

  面试题45 : 把数组排成最小的数

第6章 面试中的各项能力

第7章 两个面试案例


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

解题思路
  这题的思路还是比较难想到的。
  数组中每个数的长度可能不一致,这是排序的难点,设想每个数长度都一致,那么排序后直接将小的数放前面,大的数放后面就行了。所以一个想法是将数组中所有数都变成同一长度,例如将题目中数组的每个数都变成三位数。
  现在的问题是一位数如何变成三位数。比如3变成3xx,后面两位如何确定?
  我们可以从结果推回来,已知3排在32后面,所以3xx比32x要大,如果数组中有一个35,那么3应该排在35前面,所以3xx比35x要小,这时我们可以大胆的猜想3xx就是333。
  进一步,我们猜想所有后面补齐的数字就是该数的最后一位。为什么要这么做,就很难证明了。。。
  有了前面的思路,代码就很好写了。将补齐后的数字和原数字组合为一个集合,存储到列表中,然后对列表排序,最后依序取出原数字即可。

实战

class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ''
        lst = []
        max_len = len(str(max(numbers)))
        for i in range(len(numbers)):
            digit = numbers[i] % 10
            key = str(numbers[i]) + (max_len-len(str(numbers[i])))*str(digit)
            lst.append((key, numbers[i]))
        results = ''
        lst = sorted(lst, key=lambda x: x[0])
        for key, val in lst:
            results += str(val)
        return int(results)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16