剑指offer之032-把数组排成最小的数

题目描述

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

思路

本题主要是找排序方法判断所有数的顺序方法。

思路1

  • 1.全部用个位数+长度补齐,比如{3, 32, 321}补齐成{3331, 3222, 3213},{1, 11, 111}补齐成{1111, 1112, 1113} o(nlogn)
  • 2.排序,从小到大取下标 o(nlogn)
  • 3.根据下标的数组装结果

思路2

  • 1.比较n1与n2,转成字符串s1与s2
  • 2.比较s1s2与s2s1大小,小的放前面
  • 3.依次输出所有字符串
#思路一
def number_len(n):
    res = 0
    while n:
        n //= 10
        res += 1
    return res


def PrintMinNumber(numbers):
    # write code here
    if len(numbers) == 1: return numbers[0]
    max_len = number_len(max(numbers))
    map = {}
    for i in range(len(numbers)):
        n = numbers[i]
        pad = n % 10
        n_len = number_len(n)
        for j in range(max_len-n_len):
            n = n*10+pad
        map[n*10+n_len] = i
    keys = sorted(map.keys())
    res = numbers[map[keys[0]]]
    for i in range(1, len(keys)):
        n = numbers[map[keys[i]]]
        res = res * 10 ** number_len(n) + n
    return res



    # map = {numbers[i]:i for i in range(len(numbers))}

print(PrintMinNumber([11,1,111]))
#思路2:
import functools
def compare(s1, s2):
    if s1+s2 < s2+s1:
        return -1
    elif s1+s2 == s2+s1:
        return 0
    else:
        return 1

def PrintMinNumber(numbers):
    # write code here
    if not numbers: return ''
    if len(numbers) == 1: return numbers[0]
    str_numbers = [str(n) for n in numbers]

    return ''.join(sorted(str_numbers, key=functools.cmp_to_key(compare)))

print(PrintMinNumber([32, 3, 321]))
    

关于明柳梦少

坚守自己的原则,不随波逐流。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注