Сортировка чисел в массиве без изменения положения четных чисел с помощью Java -8

Question

Я учу Java 8 потоков. Подскажите пожалуйста, как можно более компактно написать sortArray метод?

import org.junit.Test;    
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import static org.junit.Assert.assertArrayEquals;

public class TestStream {

    /*
     * Sort numbers in an array without changing even numbers position
     */

    @Test
    public void test_1() {
        int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};
        int[] expected = new int[]{1, 4, 3, 2, 5, 6, 7, 8, 9, 0};

        Integer[] arr = sortArray(nonSorted);
        int[] sorted = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sorted[i] = arr[i];
        }

        assertArrayEquals(expected, sorted);
    }

    private Integer[] sortArray(int[] array) {
        Map<Integer, Integer> even = extractEven(array);
        Integer[] withoutEvens = removeEven(array);
        int length = even.size() + withoutEvens.length;
        Integer[] result = new Integer[length];
        Arrays.sort(withoutEvens);
        for (int i = 0; i < withoutEvens.length; i++) {
            result[i] = withoutEvens[i];
        }
        even.forEach((k, v) -> {
            System.arraycopy(result, k, result, k + 1, length - k - 1);
            result[k] = v;
        });

        return result;
    }


    private Map<Integer, Integer> extractEven(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                map.put(i, array[i]);
            }
        }

        return map;
    }

    private Integer[] removeEven(int[] array) {
        ArrayList<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                list.add(array[i]);
            }
        }

        Integer[] a = new Integer[list.size()];
        return list.toArray(a);
    }
}

Answer 1

Можно придумать решение вроде: сначала мы извлекаем нечетные целые числа из nonSorted[] и помещаем их в stack отсортированным образом.

Почему мы должны использовать stack отсортированным способом ??

Конечный массив должен быть отсортирован по нечетному Integers принципу, стек следует политике FIFO (First in Last Out).

Теперь мы берем Instream и запускаем его с 0 до nonSorted.length-1 и проверяем оригинал nonSorted на нечетное Integer; как только мы найдем его, мы заменим его первым элементом стека и pop() элементом из stack.

Примечание: Нужно поиграться не каждый раз, когда вам понадобятся отсортированные элементы в стеке, но в случае с OP это происходит так:

int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};

LinkedList<Integer> stack = Arrays.stream(nonSorted)
            .sorted().filter(s -> s % 2 != 0).boxed()
            .collect(Collectors.toCollection(LinkedList::new));

int[] expected = IntStream.rangeClosed(0, nonSorted.length - 1)
       .map(s -> nonSorted[s] % 2 != 0 ? stack.pop():nonSorted[s]) 
       .toArray();

Answer 2

Мне очень понравилась идея использования отсортированного Stack, но его нелегко распараллелить, и мне стало любопытно, как это решить.

Моя идея состоит в сортировке индексов неравномерных элементов и в зависимости от положения индекса мы можем различить guish при создании массива результатов, если число четное или нет.

public int[] sortUnevenElements(int[] nonSorted) {
    int[] unevenIndices = IntStream.range(0, nonSorted.length).filter(i -> nonSorted[i] % 2 != 0).toArray();
    int[] sortedUnevenIndices = Arrays.stream(unevenIndices, 0, unevenIndices.length).boxed()
          .sorted(Comparator.comparingInt(i -> nonSorted[i])).mapToInt(Integer::intValue).toArray();
    return IntStream.range(0, nonSorted.length).map(i -> {
        int idx = Arrays.binarySearch(unevenIndices, i);
        return idx >= 0 ? nonSorted[sortedUnevenIndices[idx]] : nonSorted[i];
    }).toArray();
}

Answer 3

Я полагаю, что вы подразумеваете под Java -8 использование Stream s и других API, представленных с этого выпуска. У вас уже есть очень хорошо работающий код, по моему мнению. Я мог бы подумать о том, чтобы разбить проблему следующим образом:

1. Найти нечетные и четные числа и их сопоставления с текущими индексами. Так, чтобы четные значения с их индексами оставались фиксированными.

2. По нечетным числам и их индексам переназначали значения, сортируя их естественным образом.

3. Как только все это будет сделано, объедините эти разделенные нечетно-четные карты на основе индексов.

4. Извлеките значения из этого объединенного результата.

Общая реализация этого будет выглядеть примерно так -

private Integer[] sortArrayStream(Integer[] array) {
    Map<Boolean, Map<Integer, Integer>> evenOdds = IntStream.range(0, array.length)
            .boxed()
            .collect(Collectors.partitioningBy(i -> array[i] % 2 == 0,
                    Collectors.toMap(o -> o, i -> array[i]))); //1

    Map<Integer, Integer> oddSorted = remapWithSorting(evenOdds.get(Boolean.FALSE)); // 2

    Map<Integer, Integer> overall = new HashMap<>(evenOdds.get(Boolean.TRUE));
    overall.putAll(oddSorted); // part of 3

    return overall.entrySet().stream()
            .sorted(Map.Entry.comparingByKey()) // remaining of 3
            .map(Map.Entry::getValue) // 4
            .toArray(Integer[]::new); 
}


private Map<Integer, Integer> remapWithSorting(Map<Integer, Integer> initialIndexMapping) {
    List<Integer> oddIndexes = new ArrayList<>(initialIndexMapping.keySet());
    List<Integer> sortedOdds = initialIndexMapping.values().stream()
            .sorted().collect(Collectors.toList());
    return IntStream.range(0, sortedOdds.size())
            .boxed()
            .collect(Collectors.toMap(oddIndexes::get, sortedOdds::get));
}

Answer 4

Это пробная версия с потоками. Массив nonSorted передается в поток и собирается в new int[]. Если значение из массива nonSorted четное, оно просто копируется, в противном случае, если оно нечетное, сортировка вставки выполняется только для нечетных значений, уже присутствующих в результате.

int[] sort = IntStream.range(0, nonSorted.length)
            .collect(() -> new int[nonSorted.length], (ints, i) -> {
                ints[i] = nonSorted[i];
                if (nonSorted[i] % 2 != 0) {
                    AtomicInteger current = new AtomicInteger(i);
                    IntStream.iterate(i - 1, 
                                     (v) -> current.get() > 0 && v >= 0,
                                     (v) -> --v)
                            .forEach(ind -> {
                                if (ints[ind] % 2 != 0) {
                                    if (ints[ind] > nonSorted[i]) {
                                        ints[current.get()] = ints[ind];
                                        ints[ind] = nonSorted[i];
                                        current.set(ind);
                                    } else {
                                        current.set(-1);
                                    }
                                }
                            });
                }
            }, (a1, a2) -> {
            });