Нужна помощь в понимании алгоритма, который использует 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

Вы можете написать a+b до b+a.Но тогда вам придется переключить аргументы метода compare на b, а затем a.Но вот причина всего этого.

Во-первых, вам нужно PRETEND , чтобы strings можно было сравнить с ints, используя <и>.

Где-то вВ методе сортировки у вас есть конструкция, которая сравнивает два значения 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, как указано выше, чтобы получить восходящий или нисходящий порядок сцепленных строк.

Вот простой метод сортировки идва 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;
            }
         }
      }
   }
}

Answer 2

A и B являются строками при их сравнении, поэтому они не добавляются численно, а объединяются с использованием конкатенации строк.CompareTo затем смотрит на символы в строках и сравнивает их.

Т.е. если a = 1 и b = 2, то на самом деле это a = "1" и b = "2", поэтому a + b = "1" + "2" = "12"