劍指 Offer 45. 把數組排成最小的數

劍指 Offer 45. 把數組排成最小的數

輸入一個非負整數數組,把數組裡所有數字拼接起來排成一個數,打印能拼接出的所有數字中最小的一個。

示例 1:

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

示例 2:

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

提示:

  • 0 < nums.length <= 100

說明:

  • 輸出結果可能非常大,所以你需要返回一個字符串而不是整數
  • 拼接起來的數字可能會有前導 0,最後結果不需要去掉前導 0

做題思路:

其實做這道題,建議先看一下左神的快排代碼,了解一下快排代碼的套路。

package basic_class_01;

import java.util.Arrays;

public class Code_04_QuickSort {

	public static void quickSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		quickSort(arr, 0, arr.length - 1);
	}

	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
	}

	public static int[] partition(int[] arr, int l, int r) {
		int less = l - 1;
		int more = r;
		while (l < more) {
			if (arr[l] < arr[r]) {
				swap(arr, ++less, l++);
			} else if (arr[l] > arr[r]) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		swap(arr, more, r);
		return new int[] { less + 1, more };
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

然後把快排的思路學習到了,以後再來仔細看這道題的做題思路。

比如,【30,3】,「30」+「3」=「303」 <「3」 + 「30」 =330這個可以看出30應該排在3後面。

可以得出它的排序規則如下:

  • 若拼接的字符串x+y>y+x,則x大於y,即x在y的前面
  • 反之,x+y<y+x,則x小於y,即x在y的後面

x小於y代表:排序完成後,x在y左邊;否則反之。

圖片源自@jyd

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 res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }

    public void quickSort(String[] strs, int low, int high) {
        if (low < high) {
            int middle = getMiddle(strs, low, high);
            quickSort(strs, low, middle - 1);
            quickSort(strs, middle + 1, high);
        }
    }

    public int getMiddle(String[] strs, int low, int high) {
        //數組的第一個數為基準元素
        String temp = strs[low];
        while (low < high) {
            //從後向前找比基準小的數
            while (low < high && (strs[high] + temp).compareTo(temp + strs[high]) >= 0)
                high--;
            //把比基準小的數移到低端
            strs[low] = strs[high];
            //從前向後找比基準大的數
            while (low < high && (strs[low] + temp).compareTo(temp + strs[low]) <= 0)
                low++;
            //把比基準大的數移到高端
            strs[high] = strs[low];
        }
        strs[low] = temp;
        return low;
    }
}

這位(logiLong – 力扣(LeetCode) (leetcode-cn.com))力友根據快排思路寫的代碼如下,可以與左神的快排代碼相對照:

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]);
        }
        sort(strs, 0, strs.length - 1);
        StringBuilder ans = new StringBuilder();
        for(String s : strs)
            ans.append(s);
        return ans.toString();
    }

    // 下面是快排的代碼
    private void sort(String[] arr, int start, int end){
        if(start >= end) return;

        int pivot = partition(arr, start, end);
        sort(arr, start, pivot - 1);
        sort(arr, pivot + 1, end);
    }
    private int partition(String[] arr, int start, int end){
        int pivot = end; // 默認選取最後一個作為基準
        int i = start;
        for(int j = start; j < end; j++){
            if((arr[j] + arr[pivot]).compareTo(arr[pivot] + arr[j]) < 0) {
                if(i != j) swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, pivot);
        return i;
    }
    private void swap(String[] arr, int index1, int index2){
        String temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

這是K神的代碼,可以在面試的時候快速的寫出。

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 res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}

當然也可以採用內置函數的方式,代碼如下:

  • Java 定義為 (x, y) -> (x + y).compareTo(y + x)

但是不建議面試的寫。

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]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

參考鏈接:

//leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/offer45ba-shu-zu-pai-cheng-zui-xiao-de-s-eh8d/

//leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/ 2