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

本问题对应的 leetcode 原文链接:剑指 Offer 45. 把数组排成最小的数
对应打卡问题:【排序算法运用】剑指 Offer 45. 把数组排成最小的数

问题描述

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

示例 1:

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

示例 2:

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

提示:

  • 0 < nums.length <= 100

说明:

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

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
 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]);
        }

        quickSort(strs, 0, strs.length - 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }
///时间nlogn,空间 On
    // 快速排序模版(和普通快速排序模版一样的,除了比较那里不一样)
    private void quickSort(String[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);

    }

    int partition(String[] arr, int left, int right){
       String pivot = arr[left]; // 中间值
        int i = left;
        int j = right;

        while (i < j) {
            while (i <= j && (arr[i] + pivot).compareTo(pivot + arr[i]) <= 0) {
                i++;
            }

            while (i <= j && (arr[j] + pivot).compareTo(pivot + arr[j]) >= 0) {
                j--;
            }
            if(i >= j){
                break;
            }
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = pivot;

        return j;

    }
}

时间复杂度:O(nlogn)
额外空间复杂度:O(n)

发表回复

后才能评论