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

难度: 🌕🌗

问题描述

---

解法 1 - Arrays.sort()

class Solution {
    public String minNumber(int[] nums) {
        // 思路：
        // 关键是找到规律 a + b > b + a 的字符串拼接
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0; i < len; i ++) {
            arr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(arr, (a, b) -> {
            return (a + b).compareTo(b + a);
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i ++) {
            sb.append(arr[i]);
        }
        return sb.toString();
    }
}

---

输出 1

---

解法 2 - 快排

class Solution {
    public String minNumber(int[] nums) {
        // 思路：
        // 快排
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0; i < len; i ++) {
            arr[i] = String.valueOf(nums[i]);
        }
        mySol(arr, 0, len - 1);
        StringBuilder sb = new StringBuilder();
        for(String str: arr) {
            sb.append(str);
        }
        return sb.toString();
    }

    private void mySol(String[] arr, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        String monitor = arr[left];
        int i = left;
        int j = right;
        while(i < j) {
            while(i < j && (arr[j] + monitor).compareTo(monitor + arr[j]) >= 0) {
                j --;
            }
            while(i < j && (arr[i] + monitor).compareTo(monitor + arr[i]) <= 0) {
                i ++;
            }
            swap(arr, i, j);
        }
        swap(arr, left, i);
        mySol(arr, left, i - 1);
        mySol(arr, i + 1, right);
    }

    private void swap(String[] arr, int a, int b) {
        String tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

---

输出 2

---

解法 3 - 归并排序

class Solution {
    public String minNumber(int[] nums) {
        // 思路：
        // 归并排序
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0; i < len; i ++) {
            arr[i] = String.valueOf(nums[i]);
        }
        mySol(arr, 0, len - 1);
        StringBuilder sb = new StringBuilder();
        for(String str: arr) {
            sb.append(str);
        }
        return sb.toString();
    }

    private void mySol(String[] arr, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mySol(arr, left, mid);
        mySol(arr, mid + 1, right);
        // 合并
        merge(arr, left, mid, right);
    }

    private void merge(String[] arr, int left, int mid, int right) {
        int len = right - left + 1;
        String[] res = new String[len]; // 暂存排序好的新数组
        int index = 0;
        int i = left;
        int j = mid + 1;

        while(i <= mid && j <= right) {
            if((arr[i] + arr[j]).compareTo(arr[j] + arr[i]) <= 0) {
                res[index] = arr[i];
                index ++;
                i ++;
            } else {
                res[index] = arr[j];
                index ++;
                j ++;
            }
        }
        while(i <= mid) {
            res[index] = arr[i];
            index ++;
            i ++;
        }
        while(j <= right) {
            res[index] = arr[j];
            index ++;
            j ++;
        }
        for(int k = 0; k < len; k ++) {
            arr[k + left] = res[k];
        }
    }
}

---

输出 3

---

解法 4 - 堆排

class Solution {
    public String minNumber(int[] nums) {
        // 思路：
        // 堆排 - 大根堆
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0; i < len; i ++) {
            arr[i] = String.valueOf(nums[i]);
        }
        // 建堆
        build(arr, len);
        // arr[0] 始终是最大的元素
        for(int i = len - 1; i > 0; i --) {
            swap(arr, i, 0);
            // 维护堆的平衡
            resize(arr, 0, i - 1);
        }
        StringBuilder sb = new StringBuilder();
        for(String str: arr) {
            sb.append(str);
        }
        return sb.toString();
    }

    private void resize(String[] arr, int left, int right) {
        // 堆顶元素判断是否下沉
        int curIndex = left;
        int lc = 2 * curIndex + 1;
        int rc = 2 * curIndex + 2; // 左右孩子节点下标
        if(lc > right) {
            return;
        }
        // lc <= right
        // 找到 左右孩子 最大的，和父节点比较，判断是否下沉
        int childIndex = lc;
        if(rc <= right && (arr[rc] + arr[lc]).compareTo(arr[lc] + arr[rc]) > 0) {
            childIndex = rc;
        }
        if((arr[curIndex] + arr[childIndex]).compareTo(arr[childIndex] + arr[curIndex]) < 0) {
            // 下沉
            swap(arr, curIndex, childIndex);
            curIndex = childIndex;
            resize(arr, childIndex, right);
        }
    }

    private void build(String[] arr, int len) {
        for(int i = 1; i < len; i ++) {
            // 判断是否需要上浮
            int curIndex = i;
            int parentIndex = (curIndex - 1) >> 1;
            while(curIndex > 0 && (arr[curIndex] + arr[parentIndex]).compareTo(arr[parentIndex] + arr[curIndex]) > 0) {
                // 上浮
                swap(arr, curIndex, parentIndex);
                curIndex = parentIndex;
                parentIndex = (curIndex - 1) >> 1;
            }
        }
    }

    private void swap(String[] arr, int a, int b) {
        String tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

---

输出 4