[Swordfinger offer] Minimize the number of arrays

 

Title Description

Input a positive integer array, splice all the numbers in the array into one number, print the smallest of all the numbers that can be spliced. For example, the input array {3, 32, 321} prints out the minimum number of the three numbers that can be arranged as 32123.

Solving problems

First, the array is converted into string array, then the string array is sorted according to the rules, and finally the ordered string array is stitched together.
The key is to establish a sort rule:

  • If a b > b a, a > b
  • If a B < B a, a < B
  • If a B = B a, a = b

Explanation:
a = 21
b = 2
Because 212 < 221, a B < B a, a < B
So by comparing the size of a b and b a, we can judge whether a is in front or b is in front.

For comparators, for example, {3, 32, 321} array in the example is first put in 3, then 3 and 32, because 332 > 323, so 3 > 32 array is now [32, 3]; then add 321 to the array, first compared with 32, 32132 < 323232321, so 321 < 32, so 321 should be in front of 32, and then compared with 3, 3213 < 3321, so 321 < 3 array is finally sorted [321, 32, 3].

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int len = numbers.length;
        if(len==0)
            return "";
        if(len==1)
            return String.valueOf(numbers[0]);
        String[] str = new String[len];
        for(int i=0;i<len;i++)
            str[i] = String.valueOf(numbers[i]);
        Arrays.sort(str,new Comparator<String>(){
            public int compare(String st1,String st2){
                String s = st1+st2;
                String t = st2+st1;
                return s.compareTo(t);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(String st:str){
            sb.append(st);
        }
        return sb.toString();

    }
}

Although the comparator is hard to think of, the idea of comparing two strings together is still good. We can combine two values by ourselves and decide which value to put in front by comparing the size. Based on the idea of bubble sorting, the smallest landing is sorted once, and then the sorting is continued.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
    for(int i=0;i<numbers.length;i++){//The smallest landing after a sequence
        for(int j=i+1;j<numbers.length;j++){
            int a = Integer.valueOf(numbers[i]+""+numbers[j]);
            int b = Integer.valueOf(numbers[j]+""+numbers[i]);
            if(a>b){
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
    }
    StringBuilder sb = new StringBuilder();
        for(int i=0;i<numbers.length;i++){
            sb.append(numbers[i]);
        }
        return sb.toString();
    }
}

 

Tags: Java

Posted on Sun, 06 Oct 2019 15:24:42 -0700 by Addos