Взвешенный порядок списка с нулем - PullRequest
Новая
       29

Взвешенный порядок списка с нулем

0 голосов
/ 04 февраля 2020

Я пытался реализовать класс Comparator, который должен упорядочивать список в зависимости от веса позиции. Я объясню, что я должен сделать sh.

Предположим, у меня есть ArrayList<T>. Этот список массивов всегда имеет фиксированный размер, заполняя другой слот значениями null. 

//fixed size = 3
T myObj1, myObj2;
[myObj1, null, myObj2];

В этом примере myObj2 < myObj1, поскольку он хранится в слоте, значение позиции которого меньше первого .

Компаратор упорядочения должен выдавать следующие выходные данные: 

//fixed size = 3
T myObj1, myObj2;
[myObj1, myObj2, null];

Другие примеры: 

//fixed size = 7;
T myObj1, myObj2, myObj3, myObj4;
INPUT = [myObj1, null, null, myObj4, myObj3, myObj2, null];
RESULT = [myObj1, myObj4, myObj3, myObj2, null, null, null];

Я думал об использовании Comparator<T> (T - это спецификация c класс, он не должен быть общим на самом деле); Есть ли способ повторить такое поведение?

Ответы [ 3 ]

1 голос
/ 04 февраля 2020

Вместо написания собственной логики компаратора c обычно проще использовать один из вспомогательных методов, например Comparator.comparing. 

> List<Integer> foo = Arrays.asList(1, null, 2, null, 1, null);
> Collections.sort(foo, Comparator.comparing(x -> x == null ? 1 : 0));
> foo
[1, 2, 1, null, null, null]

Таким образом, сортировка делается так, как если бы все ненулевые элементы были равны 0, а нулевые - 1, поэтому после сортировки нулевые элементы будут появляться после ненулевых. Элементы, не равные NULL, останутся в их первоначальном порядке, поскольку Collections.sort стабильно.

Для этого конкретного c случая, как отмечает @Zabuza, вспомогательный метод Comparator.nullsLast делает абсолютно правильные вещи; аргументом является null, потому что нет компаратора «отступления», который мы хотим использовать для ненулевых элементов. 

> Collections.sort(foo, Comparator.nullsLast(null));

Тем не менее, это решение занимает O (n log n) время для списка длина n, когда решение с двумя указателями может решить ту же проблему за время O (n).

1 голос
/ 04 февраля 2020

Вы всегда можете сделать возврат нулей> 0 в компараторе 

if (one == null && two == null) {
    return 0;
} else if (two == null) {
    return -1;
} if (one == null) {
    return 1;
} else {
   //Compare logic...
}

Это говорит о том, что нули "больше", чем ненулевые значения

0 голосов
/ 04 февраля 2020

Для любого нуждающегося я понял это благодаря @ tomgeraghty3 

public class TComparator implements Comparator<T> {
    public int compare(T r1, T r2) {
        if (r1 == null && r2 == null) {
            return 0;
        } else if (r2 == null) {
            return -1;
        } if (r1 == null) {
            return 1;
        } else {
           return 1;
        }
    }
}
...