Как правильно возвратить список медиан другого списка

Question

В моем коде я хочу найти медиану одного списка и вставить в другой список и удалить значение медианы в изначальном листе, и делать это пока в изначальном списке не останутся значения, по примеру: в листе есть например значения[0, 1, 2, 3, 4], я нахожу медиану по индексу int median = temp.size() / 2, в данном случае это 2 и возвращает значение в индексе 2 = 2, этот индекс со значением удаляется и остается следующие значения в листе [0, 1, 3, 4], тут нахожу медиану, в данном случае int median = temp.size() / 2 тоже 2, но у нас четное количество значений, а в этом случае код должен возвратить самое маленькое значение сравнив значение median и median-1, сравнив значение 3 и 1 он должен возвратить 1 и так далее... В моем коде первую медиану находит - 2, но потом выдает -1 и не понимаю как решить проблему. Может неправильно сравниваю значения temp.indexOf(median) < temp.indexOf(median - 1)

List<Integer> temp = new ArrayList();
        List<Integer> medianTemp = new ArrayList();
int listMedian;
        while (temp.size() != 0) {
            int median = temp.size() / 2;
            if (temp.size() != 1) {
                if (temp.size() % 2 == 0) {
                    if (temp.indexOf(median) < temp.indexOf(median - 1)) {
                        listMedian = temp.indexOf(median);
                        medianTemp.add(listMedian);
                        temp.remove(median);
                    } else {
                        listMedian = temp.indexOf(median - 1);
                        medianTemp.add(listMedian);
                        temp.remove(median);
                    }
                } else {
                    listMedian = temp.indexOf(median);
                    medianTemp.add(listMedian);
                    temp.remove(median);
                }
            } else {
                listMedian = temp.indexOf(median);
                medianTemp.add(listMedian);
                temp.remove(median);
            }

        }
        System.out.println(medianTemp);

Answer 1

temp.indexOf(индекс) - бесмыссленная конструкция. Вам нужно обратится к элементу списка по индексу. Сделайте так: temp.get(индекс).

Когда вы поправите ваш код, он заработает. Однако его можно улучшить. Если вы знаете что такое О-большое, то понимаете что конструкция temp.remove(индекс) тратит линейное время если удаление делается из середины списка. Всего ваша программа потратит квадратичное время на вывод медиан.

Можно обойтись без удаления элементов, если поддерживать "дырку" из ранее удалённых медиан. В коде ниже эта дырка занимает интервал индексов (l, r). Чтобы выбрать следующую медиану нужно сравнить длину оставшихся хвостов слева и справа от дырки. Если они не равны, то нужно вывести элемент из длиннейшего хвоста. Если хвосты равны, сравниваем элементы на краях дырки (индексы l и r) и выводим меньший.

Как только элемент выведен, соответствующий край дырки подвигается.

Остались мелочи: правильно задать пустую дырку (l = r - 1) в начале и вовремя завершить цикл (когда оба хвоста опустели). И добавить обработку пустого списка на всякий случай.

То что получилось работает за линейное время:

import java.util.ArrayList;
import java.util.List;


class MedianPrinter {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < args.length; ++i) {
            list.add(Integer.parseInt(args[i]));
        }

        List<Integer> medians = new ArrayList<Integer>();

        int n = list.size();
        if (n > 0) {
            int l = (n - 1) / 2;
            int r = n - n / 2;

            while (0 <= l || r <= n - 1) {
                if (l + 1 > n - r) {
                    medians.add(list.get(l));
                    --l;
                } else if (l + 1 < n - r) {
                    medians.add(list.get(r));
                    ++r;
                } else {
                    if (list.get(l) <= list.get(r)) {
                        medians.add(list.get(l));
                        --l;
                    } else {
                        medians.add(list.get(r));
                        ++r;
                    }
                }
            }
        }

        for (int v : medians) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

$ javac MedianPrinter.java

$ java MedianPrinter 0 1 2 3 4
2 1 3 0 4 

$ java MedianPrinter 0 1 2 3 4 5
2 3 1 4 0 5

БЛОГ НА HUSL

Как правильно возвратить список медиан другого списка

Ответы (1 шт):