对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（先入后出退出）政策。

现在我们取一个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

[我相信您对Java-8的理解是使用了Stream和自该版本以来引入的其他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 3

我真的很喜欢使用排序的Stack的想法，但是它不容易并行化，让我很好奇如何解决。

我的想法是对不均匀元素的索引进行排序，并根据在结果数组创建过程中可以区分的索引位置。

int[] nonSorted = {11, 3, 4, 5, 2, 1, 6, 9, 8, 7, 0, 101};
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();
int[] sorted = IntStream.range(0, nonSorted.length).map(i -> {
    int idx = Arrays.binarySearch(unevenIndices, i);
    return idx >= 0 ? nonSorted[sortedUnevenIndices[idx]] : nonSorted[i];
}).toArray();