题解 | #最大数#

最大数

http://www.nowcoder.com/practice/fc897457408f4bbe9d3f87588f497729

 /**
     * 练习下快速排序
     *
     * @param nums
     * @return
     */
    public static String solve(int[] nums) {
        // write code here
        quickSort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        int i = 0;
        for (int value : nums) {
            if (value == 0) {
                i++;
            }
            sb.append(value);
        }
        if (i == nums.length) {
            return "0";
        }
        return sb.toString();
    }

    private static void quickSort(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        int p = partiton(nums, low, high);
        quickSort(nums, low, p - 1);
        quickSort(nums, p + 1, high);
    }

    private static int partiton(int[] nums, int low, int high) {
        int tmp = nums[low];
        while (low < high) {
            while (low < high && alowb(nums[high], tmp)) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && !alowb(nums[low], tmp)) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = tmp;
        return low;
    }

    private static boolean alowb(int num, int tmp) {
        // num>tmp
        String a = Integer.toString(num);
        String b = Integer.toString(tmp);
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        int i = 0;
        int j = 0;
        while (i < ac.length && j < bc.length) {
            if (ac[i] > bc[j]) {
                return false;
            } else if (ac[i] == bc[j]) {
                i++;
                j++;
            } else {
                return true;
            }
        }
        if (j < bc.length) {
            if (bc[j] == '0') {
                return false;
            } else {
                return bc[j] > ac[0];
            }
        }
        if (i < ac.length) {
            if (ac[i] == '0') {
                return true;
            } else {
                return ac[i] < bc[0];
            }
        }
        return false;
    }
算法 文章被收录于专栏

数据结构和算法

全部评论

相关推荐

3 收藏 评论
分享
牛客网
牛客企业服务