把数组排成最小的数

把数组排成最小的数

http://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993

把数组排成最小的数
数据处理:将数字化为字符串
排序规则: a + b < b + a
排序实现:1、使用工具类 2、手写排序
1、快排+自定义排序规则

public class Solution {
    public String PrintMinNumber(int[] nums) {
        // a < b => a + b < b + a
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = nums[i] + "";
        }
        quickSort(strs, 0, n - 1);
        StringBuilder sb = new StringBuilder();
        for (String item : strs) {
            sb.append(item);
        }
        return sb.toString();
    }

    private void quickSort(String[] nums, int left, int right) {
        if (left >= right) return;
        int index = partition(nums, left, right);
        quickSort(nums, left, index - 1);
        quickSort(nums, index + 1, right);
    }

    private int partition(String[] nums, int left, int right) {
        if (left >= right) return left;
        String value = nums[left];
        int start = left, end = right + 1;
        while (start < end) {
            while ((nums[++start] + value).compareTo(value + nums[start]) < 0) {
                if (start >= right) break;
            }
            while ((nums[--end] + value).compareTo(value + nums[end]) > 0) {
                if (end <= left) break;
            }
            if (start >= end) break;
            swap(nums, start, end);
        }
        swap(nums, left, end);
        return end;
    }

    private void swap(String[] nums, int left, int right) {
        if (left >= right) return;
        String temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

2、Arrays工具类+自定义比较器

    public String PrintMinNumber(int[] nums) {
        // a < b => a + b < b + a
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = nums[i] + "";
        }
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (String item : strs) {
            sb.append(item);
        }
        return sb.toString();
    }
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务