Наиболее эффективный способ слияния с двумя отсортированными связанными списками Java (не пользовательскими связанными списками) - PullRequest
Новая
       3

Наиболее эффективный способ слияния с двумя отсортированными связанными списками Java (не пользовательскими связанными списками)

0 голосов
/ 22 ноября 2018

если метод объединяет два отсортированных списка, а подпись выглядит следующим образом, кто-то может передать связанный список, и если вы используете a.get (index), общая сложность времени выполнения будет O (N ^ 2).Похоже, что итераторы - единственный способ получить O (N) время выполнения.Но это делает код немного неуклюжим.Есть ли способ упростить этот код при сохранении времени выполнения O (N)?Спасибо за вашу помощь! 

 public static List<Integer> mergeListEfficient(List<Integer> a, List<Integer> b) {
    List<Integer> result = new ArrayList<>();
    Iterator<Integer> firstItr = a.iterator();
    Iterator<Integer> secondItr = b.iterator();
    Integer firstVal = firstItr.hasNext() ? firstItr.next() : null;
    Integer secondVal = secondItr.hasNext() ? secondItr.next() : null;

    while (firstVal != null || secondVal != null) {
        if (firstVal != null && secondVal != null) {
            if (firstVal < secondVal) {
                result.add(firstVal);
                firstVal = firstItr.hasNext() ? firstItr.next() : null;
            } else {
                result.add(secondVal);
                secondVal = secondItr.hasNext() ? secondItr.next() : null;
            }
        } else if (firstVal != null) {
            result.add(firstVal);
            firstVal = firstItr.hasNext() ? firstItr.next() : null;
        } else {
            result.add(secondVal);
            secondVal = secondItr.hasNext() ? secondItr.next() : null;
        }
    }

    return result;
}

public static void main(String args[]) throws InterruptedException {
    List<Integer> a = new java.util.LinkedList<>();
    a.add(2);
    a.add(3);
    a.add(5);

    List<Integer> b = new java.util.LinkedList<>();
    b.add(3);
    b.add(5);
    b.add(6);

    System.out.println(mergeListEfficient(a, b));
    //prints correctly [2, 3, 3, 5, 5, 6]
}

1 Ответ

0 голосов
/ 22 ноября 2018

Я предлагаю ввести новый класс с интерфейсом, который лучше подходит для этой задачи. 

public class App {
    public static List<Integer> mergeListEfficient(List<Integer> a, List<Integer> b) {
        List<Integer> result = new ArrayList<>();
        BetterIterator firstItr = new BetterIterator(a.iterator());
        BetterIterator secondItr = new BetterIterator(b.iterator());

        while (firstItr.hasValue() && secondItr.hasValue()) {
            Integer firstVal = firstItr.getValue();
            Integer secondVal = secondItr.getValue();
            if (firstVal < secondVal) {
                result.add(firstVal);
                firstItr.move();
            } else {
                result.add(secondVal);
                secondItr.move();
            }
        }
        for(;firstItr.hasValue();firstItr.move()){
            result.add(firstItr.getValue());
        }
        for(;secondItr.hasValue();secondItr.move()){
            result.add(secondItr.getValue());
        }

        return result;
    }

    private static class BetterIterator {

        private final Iterator<Integer> iterator;

        private boolean hasNext;
        private Integer value;

        public BetterIterator(Iterator<Integer> iterator) {
            this.iterator = iterator;
            move();
        }

        public boolean hasValue() {
            return hasNext;
        }

        public Integer getValue() {
            return value;
        }

        public void move() {
            hasNext = iterator.hasNext();
            if (hasNext) {
                value = iterator.next();
            }
        }
    }

    public static void main(String args[]) {
        List<Integer> a = new java.util.LinkedList<>();
        a.add(2);
        a.add(3);
        a.add(5);

        List<Integer> b = new java.util.LinkedList<>();
        b.add(3);
        b.add(5);
        b.add(6);

        System.out.println(mergeListEfficient(a, b));
        //prints correctly [2, 3, 3, 5, 5, 6]
    }
}

PS: Если вы позволили изменить свой ввод, вы можете упростить этот код.

Вы можете избавиться от BetterIterator:

  • BetterIterator.hasValue стать !a.isEmpty()
  • BetterIterator.getValue стать a.get(0)
  • BetterIterator.move стать a.remove(0)
...