把数组排成最小的数java如何实现?

KLQ 2020-04-16 13:57:07 java常见问答 5098

下面给大家分享的是把数组排成最小的数的java实现及思想有哪些实现方法呢?感兴趣的小伙伴可以一起来了解一下。

题目:

输入一个正整数数组,将数组当中所有的数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

例:

输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

思路1

代码实现:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution
{
    public String PrintMinNumber(int[] numbers)
    {
        int n;
        String s = "";
        ArrayList < Integer > list = new ArrayList < Integer > ();
        n = numbers.length;
        for (int i = 0; i < n; i++)
        {
            list.add(numbers[i]);
        }
        Collections.sort(list, new Comparator < Integer > ()
        {
            public int compare(Integer str1, Integer str2)
            {
                String s1 = str1 + "" + str2;
                String s2 = str2 + "" + str1;
                return s1.compareTo(s2);
            }
        });
        for (int j: list)
        {
            s += j;
        }
        return s;
    }
}

思路2:

对vector容器内的数据进行排序,依照将a和b转成string之后,假如a+b

例如2 21 因为212< 221所以排序后21 2

to_string()可以将int转化成string

代码实现:

class Solution
{
    public:
        static bool cmp(int a, int b)
        {
            string A = "";
            string B = "";
            A += to_string(a);
            A += to_string(b);
            B += to_string(b);
            B += to_string(a);
            return A < B;
        }
    string PrintMinNumber(vector < int > numbers)
    {
        string answer = "";
        sort(numbers.begin(), numbers.end(), cmp);
        for (int i = 0; i < numbers.size(); i++)
        {
            answer += to_string(numbers[i]);
        }
        return answer;
    }
};

思路3:

将整型数组转换成String数组,之后将String数组排序,最后将排好序的字符串数组拼接出来。

关键就是制定排序规则。

排序规则:

若ab > ba 则 a > b;

若ab < ba 则 a < b;

若ab = ba 则 a = b;

说明:

例"3" < "31"但是 "331" > "313",所以要将二者拼接起来进行比较。

代码实现:

public String PrintMinNumber(int[] numbers)
{
    if (numbers == null || numbers.length == 0) return "";
    int len = numbers.length;
    String[] str = new String[len];
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++)
    {
        str[i] = String.valueOf(numbers[i]);
    }
    Arrays.sort(str, new Comparator < String > ()
    {
        @Override
        public int compare(String s1, String s2)
        {
            String c1 = s1 + s2;
            String c2 = s2 + s1;
            return c1.compareTo(c2);
        }
    });
    for (int i = 0; i < len; i++)
    {
        sb.append(str[i]);
    }
    return sb.toString();
}

你更喜欢那种思路呢?请继续关注本站,有更多的Java实例可以分享给大家。