“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

Enter an array of non-negative integers, concatenate all the numbers in the array into a number, and print the smallest number that can be concatenated.

  • Example 1:
Input: [10,2] output: "102"Copy the code
  • Example 2:
Input: [3,30,34,5,9] output: "3033459"Copy the code
  • prompt
0 < nums.length <= 100
Copy the code

parsing

The most important part of the problem is the custom sort. Once the singularity of the sort is found, it is easy to solve the problem. And the way we figure out which one is bigger and which one is smaller is if str1 plus str2 is greater than str2 plus str1, and it’s really that simple.

The sample

Class Solution {public String minNumber(int[] nums) {public String minNumber(int[] nums) { String[] STRS = new String[nums.length]; String[] STRS = new String[nums.length]; for(int i = 0; i < nums.length; i++) { strs[i] = String.valueOf(nums[i]); } Arrays.sort(strs, (o1, o2) -> (o1+o2).compareTo(o2+o1)); StringBuilder sb = new StringBuilder(); for (String x:strs) { sb.append(x); } return sb.toString(); }}Copy the code

Running results:

Result: Yes

Execution time: 4 ms, beating 97.52% of users in all Java commits

Memory consumption: 38 MB, beating 45.05% of all Java commits

  • Other solutions

The following method is to use random quicksort. Remember that sorting is not a simple matter of sorting a and B, such as sorting 12,543, then the comparison should be 12543 and 54312, directly find the number of digits of each number, and then add up 12000 + 54 to 54300 + 12

class Solution {
    public String minNumber(int[] nums) {
        return minNumber4(nums);
    }
    public String minNumber4(int[] nums){
       quickSortRandom(nums,0,nums.length-1);
       StringBuilder sb = new StringBuilder(nums.length);
       for(int i : nums) sb.append(i);
       return sb.toString();
    }
    public void quickSortRandom(int[] A,int low,int high){
        if(low < 0 || high >= A.length || low >= high ) return;
        int q = partition(A,low,high);
        quickSortRandom(A,low,q-1);
        quickSortRandom(A,q+1,high);
    }
    public int partition(int[] A,int low,int high){
        int rand = low + (int)(Math.random()*(high - low));
        swap(A,rand,high);
        int x = A[high],i = low - 1;
        long a,b;
        for(int j = low; j < high; j++){
            a = 10;b = 10;
            while(A[j] >= a) a *= 10;
            while(x >= b) b *= 10;
            if(A[j] * b + x <= A[j] + x * a){
                i++;
                swap(A,i,j);
            }
        }
        swap(A,i+1,high);
        return i + 1;
    }
    public void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
Copy the code