java - 需要帮助理解使用 Arrays.sort() 的算法

Question

问题

给定一个非负整数列表，将它们排列成最大的数。

例如输入:[3,30,34,5,9] 输出:“9534330”

解决方案

public class Solution {
    // DO NOT MODIFY THE LIST
    public String largestNumber(final List<Integer> a) {

    String[] arr = new String[a.size()];
    for (int i = 0; i < a.size(); i++) {
        arr[i] = String.valueOf(a.get(i));
    }


    Arrays.sort(arr, new Comparator<String>(){
        public int compare(String a, String b){
            return (b+a).compareTo(a+b);
        }
    });


    StringBuilder sb = new StringBuilder();
    for(String s: arr){
        sb.append(s);
    }

    if(sb.charAt(0) == '0'){     //check if all zeroes are there
        return String.valueOf(0);
    }

    return sb.toString();   
    }
}

这可行，但我不知道 - 我不明白 Comparator 的作用，但我知道通过交换 (b+a) 和 >(a+b) 在代码中我们将得到一个升序结果 - 但我无法理解它在内部是如何工作的。

Answer 1

你可以在b+a之前写a+b。但随后您必须将 compare 方法的参数切换为 b，然后是 a。但这就是这一切的原因。

首先，您需要假装字符串可以像整数一样使用<和>进行比较。

在排序方法中的某个位置，您有一个比较两个值 r 和 s 的构造。

当你对它们进行排序时，你会得到这样的语句

    if (r < s) {
       swap them
    }

按一个方向对它们进行排序(可能是升序)。

如果你这样做

    if (s < r) {
      swap them 
    }

将它们按另一个方向排序。

当你颠倒r和s的顺序时，这就是你正在做的事情。更改排序方向。

将它们连接在一起时，会形成两个不同的字符串 a+b 和 b+a。但过程仍然是一样的，你先从一个方向比较它们，然后再从另一个方向比较。所以本质上是，

    r = a+b
    s = b+a

然后按照上面的方法比较 r 和 s 以获得连接字符串的升序或降序。

这是一个简单的排序方法和两个用于对整数进行排序的比较器，以便您可以了解它们是如何工作的。唯一的区别在于哪个比较返回 -1 与 1。

      int[] v = { 10, 8, 2, 3, 4, 1, 7, 5, 6, 9
      };

      sort(v, new Comparator<Integer>() {
         public int compare(Integer r, Integer s) {
            if (r < s) {
               return -1;
            }
            if (r > s) {
               return 1;
            }
            return 0;
         }
      });

      System.out.println(Arrays.toString(v));

      v = new int[] { 10, 8, 2, 3, 4, 1, 7, 5, 6, 9
      };

      sort(v, new Comparator<Integer>() {
         public int compare(Integer r, Integer s) {
            if (s < r) {
               return -1;
            }
            if (s > r) {
               return 1;
            }
            return 0;
         }
      });

      System.out.println(Arrays.toString(v));
   }

   public static void sort(int[] v, Comparator<Integer> comp) {
      for (int i = 0; i < v.length - 1; i++) {
         for (int k = i + 1; k < v.length; k++) {
            if (comp.compare(v[k], v[i]) < 0) {
               int t = v[i];
               v[i] = v[k];
               v[k] = t;
            }
         }
      }
   }
}