写一个给定非负整数列表的函数，对它们进行排列，使它们形成最大可能数 [英] Write a function that given a list of non negative integers, arranges them such that they form the largest possible number

问题描述

我有以下规范：

写一个给定非负整数列表的函数，请对其进行排列，以使其形成最大可能数。例如，给定[50，2，1，9]，最大的形式为95021。

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

我的结果

我已经为解决这个问题采取了措施，但是失败了。例如，给定输入[90,91,89,999]，此代码的结果为[909199989]，但应该为[999919089]。

My Results

I have taken a stab at a solution to the problem, but it fails. For example, given the input [90,91,89,999] the result of this code is [909199989], but it should have been [999919089].

简单来说，这是基数排序的相反。

In simple words it is a reverse of radix sort.

步骤

1）根据值创建存储桶。

2）每个存储桶都有元素列表。

3）对每个存储桶中的列表进行排序。

4）以相反的顺序显示结果。

Steps
1) Based on the values create buckets.
2) Each bucket has list of elements.
3) Sort the list in each bucket.
4) Display the result in the reverse order.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Scanner;

public class ReverseMaxPossibleNumber {
    public static void main(String[] args) {
        int[] a = { 50, 2, 1, 9 };
        int len = a.length;
        String ch = "";
        List<Map<String, ArrayList<String>>> list_map = new ArrayList<Map<String, ArrayList<String>>>();
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (int i = 0; i < len; i++) {
            ch = "" + a[i];
            String str = "";
            ArrayList<String> arraylist = new ArrayList<String>();
            for (int j = 0; j < len; j++) {
                str = "" + a[j];
                if (ch.charAt(0) == str.charAt(0)) {
                    arraylist.add(str);
                    Collections.sort(arraylist);
                    map.put("" + ch.charAt(0), arraylist);
                }
            }
        }
        list_map.add(map);
        String str = "";
        for (String key : map.keySet()) {
            str = map.get(key) + str;

        }
        str = str.replaceAll("\\D+", "");
        System.out.println(str);
    }
}

推荐答案

基本上，需要以某种方式对数字进行排序以形成最大可能的数字。考虑以下逻辑：

Basically, the numbers need to be ordered in a certain way to form the maximum possible number. Consider this logic:

• 取任意两个数字 a 和 b


• 如果 ab 大于 ba ，那么 a 应该在 b 之前。对？
  
  
  
  
  • 其中 ab 是 a 和 b 并置，因此如果 a = 4 和 b = 43 那么 ab 是 443 和 ba 是 434
  
  
  • Take any 2 numbers a and b
  • If ab is bigger than ba then a should come before b. Right?
    • Where ab is a and b concatenated, so if a = 4 and b = 43 then ab is 443 and ba is 434

    您可以在一个自定义比较器，然后将其传递给 Collections.sort ，如下所示：

    You could implement this in a custom comparator, and pass it to Collections.sort, like this:

    public String maxNumber(int[] numbers) {
        // convert int[] -> List<String>
        List<String> list = new ArrayList<>(numbers.length);
        for (int num : numbers) {
            list.add(String.valueOf(num));
        }
    
        // sort using custom comparator
        Collections.sort(list, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
    
        // join sorted items, forming max possible number
        return String.join("", list);
    }
    

    使用Java 8的代码基本上是相同的：（感谢@marcospereira ！）

    Here is basically the same code using Java 8: (thanks @marcospereira!)

    public String maxNumber(Integer ... numbers) {
        return Stream.of(numbers)
                .filter(n -> n >= 0)
                .map(Object::toString)
                .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
                .collect(Collectors.joining());
    }
    

    这篇关于写一个给定非负整数列表的函数，对它们进行排列，使它们形成最大可能数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！