通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 45. 把数组排成最小的数

60人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/901

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 45. 把数组排成最小的数

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

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

0 < nums.length <= 100

说明:

  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

难度:中等;标签:排序;编程语言:JAVA


其它解法1

public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) 
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }

这题做了一点印象都没有,解法完全忘了,复习一下,数字转成字符串,字符串比较大小(连接后按ASCII码来排序),如201和20,20201大于20120,所以是201在前,20在后(既然结果是一个连接后的字符串,那我们两两连接后比较)


其它解法2

class Solution {
    public String minNumber(int[] nums) {
        fastSort(nums, 0, nums.length - 1);
        StringBuilder  sb = new StringBuilder();
        for (int i = 0; i < nums.length; i++)
            sb.append(nums[i]);
        return sb.toString();
    }

    private int compare(int o1, int o2) {
        if (o1 == 0 || o2 == 0)
            return o1 == 0 ? -1 : 1;
        return and(o1, o2) > and(o2, o1) ? 1 : -1;
    }

    private long and(int a, int b) {
        int multiplier = 1, tmp = b;
        while (tmp > 0) {
            tmp /= 10;
            multiplier *= 10;
        }
        return (long)a * multiplier + b;
    }

    private void fastSort(int[] nums, int l, int r) {
        if (r < l) return;
        int cur = l - 1;
        for (int i = l; i < r; i++) {
            // 记录符合‘小于’的位置
            if (compare(nums[i], nums[r]) >= 0 || ++cur == i)
                continue;
            // 将第一个不符合‘小于’的位置与当前符合‘小于’的位置交换
            swap(nums, cur, i);
        }
        if (++cur != r)
            swap(nums, cur, r);
        fastSort(nums, l, cur - 1);
        fastSort(nums, cur + 1, r);
    }

    private void swap(int[] nums, int n, int m) {
        nums[n] ^= nums[m];
        nums[m] ^= nums[n];
        nums[n] ^= nums[m];
    }
}

与解法1方法一样,不同的是自己写了一个快速排序的方法


亲爱的读者:有时间可以点赞评论一下

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告