Java объединяет смежные элементы массива, чтобы получить максимальное минимальное значение - PullRequest
Новая
       25

Java объединяет смежные элементы массива, чтобы получить максимальное минимальное значение

0 голосов
/ 11 января 2019

простите за запутанный заголовок, мне нужно реализовать алгоритм, который можно упростить следующим образом:

, учитывая массив целых чисел и необходимое количество слияний (обозначается как k ), возвращают максимальное минимальное значение слитого массива, слияние может происходить только с соседними элементами.

например. массив = [3,2,8,2,9], k = 2 Максимальное минимальное значение массива после двух слияний составляет 5, а объединенный массив - [5, 10, 9]. В этом примере нам нужно объединить элементы 3 & 2 и 8 & 2.

Любые другие стратегии слияния приведут к тому, что минимальное значение будет меньше или равно 5, например: [5,8,11], [3,10,11], [13,2,9] (объединенные элементы могут быть объединены снова)

Какова лучшая структура данных для представления данных и каков эффективный алгоритм для решения проблемы? Насколько я могу судить, жадный алгоритм должен применяться там, где должно происходить слияние с текущим минимальным значением массива и одним из его меньших соседних элементов.

Редактировать : Я только что понял, что жадный алгоритм может не применяться, извините за вводящий в заблуждение комментарий, если он не различает слияние с левым или правым элементами, это приведет к неправильному ответу. Возьмем это в качестве примера, учитывая массив = [4,5,3,5], и нам нужно удалить 2 элементов.

С жадным [4,5,3,5] -> [4,8,5] -> [12,5], поэтому ответ 5; однако правильный ответ должен быть 8 со следующей последовательностью слияния:

[4,5,3,5] -> [4,5,8] -> [9,8]

1 Ответ

0 голосов
/ 11 января 2019

ValPosFrom - это простой класс, который хранит эти вещи, from - это место для слияния. вы можете получить недетерминированные результаты от таких вещей, как List = 3,2,6,3,2 и k = 1, он объединит одну из 2 минут в 5, но не имеет значения, какая именно. оно сходится, когда все соседние значения позиций являются уникальными. 

    private static List<Integer> merge(List<Integer> things, int merges) {
    List<Integer> result = new ArrayList<>(things);
    for (int i = 0; i < merges; i++) {
        int min = Integer.MAX_VALUE;
        List<Integer> positions = new ArrayList<>();
        for (int j = 0; j < result.size(); j++) {
            if (result.get(j) < min) {
                positions.clear();
                positions.add(j);
                min = result.get(j);
            } else if (result.get(j) == min) {
                positions.add(j);
            }
        }
        List<ValPosFrom> neighbors = new ArrayList<>();
        positions.forEach(p -> {
            if (p - 1 >= 0) {
                neighbors.add(new ValPosFrom(result.get(p - 1), p - 1, p));
            }
            if (p + 1 < result.size()) {
                neighbors.add(new ValPosFrom(result.get(p + 1), p + 1, p));
            }
        });
        ValPosFrom vpf = Collections.min(neighbors, Comparator.comparingInt(v -> v.val));
        result.set(vpf.pos, result.get(vpf.pos) + result.get(vpf.from));
        result.remove(vpf.from);
    }
    return result;
}
...