时间戳

首页 > 解决方案 > 需要帮助理解使用 Arrays.sort() 的算法

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

问题描述

问题

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

例如输入：[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)在代码中我们将得到一个升序的结果——但我无法理解这是如何在内部工作的。

标签： javastringcomparatorcompareto

解决方案

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

首先，您需要PRETEND可以strings像ints使用 < 和 > 一样进行比较。

在 sort 方法的某处，您有一个比较两个值r和s.

当你对它们进行排序时，你有一个类似的声明

    if (r < s) {
       swap them
    }

将它们按一个方向排序（可能是升序）。

如果你这样做

    if (s < r) {
      swap them 
    }

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

r当您颠倒and的顺序时s，这就是您正在做的事情。改变排序的方向。

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

    r = a+b
    s = b+a

然后你比较r和s如上得到连接字符串的升序或降序。

这是一个简单的排序方法和两个排序方法，Comparators以便integers您了解它们是如何工作的。唯一的区别是哪个比较返回 -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;
            }
         }
      }
   }
}

推荐阅读