这种基于流的数组方法如何按 1 位的数量对 int[] 进行排序？

Question

class Solution {
    public int[] sortByBits(int[] arr) {
        return Arrays.stream(arr).boxed().sorted((a, b) -> Integer.bitCount(a) == Integer.bitCount(b) ? a - b : Integer.bitCount(a) - Integer.bitCount(b)).mapToInt(Integer::intValue).toArray();
    }
}

我刚刚开始尝试 Java 流，我发现了这个解决方案，可以在给定数组时按 1 位的数量对整数进行排序。我喜欢这个解决方案，但我不明白流被装箱后发生了什么。如果有人能分解以

.sorted(...

开头的每个步骤，我将非常感激。

也许有人可以为

.sort

正在做的事情提供更好、更容易理解的解决方案。

我对该解决方案有点不清楚的最后一件事是声明末尾的

.mapToInt(Integer::intValue)

正在做什么。具体来说

intValue

的目的是什么？

抱歉，如果我的问题看起来有点原始，我刚刚发现了流，并且看到了它的巨大潜力。我想确保我真正理解正在发生的一切。

Answer 1

稍后再介绍一点 IDE“un-lambdaing”；-)

class Solution {
  public int[] sortByBits(int[] arr) {
    return Arrays.stream(arr)
        .boxed()    // boxing for sorting with Comparator
        .sorted(new Comparator<Integer>() {
          @Override
          public int compare(Integer a, Integer b) {
            if(Integer.bitCount(a) == Integer.bitCount(b)) { 
              // if both have the same number of bits
              return a - b;    // smaller int value first
            }
            // otherwise least number of bits first
            return Integer.bitCount(a) - Integer.bitCount(b); 
          }
        })
        .mapToInt(new ToIntFunction<Integer>() { // unboxing
          @Override
          public int applyAsInt(Integer integer) {
            return integer.intValue();
          }
        }).toArray();  // array from stream
  }
}

Answer 2

Stream.sorted

方法根据给定的

Comparator

对流的元素进行排序。

根据 方法 Javadocs：

返回一个由该流的元素组成的流，根据提供的

Comparator

进行排序。

sorted

函数中的lambda表达式是

Comparator.compare

的实现，它定义了元素之间的顺序。

Comparator

比较函数，对某些对象集合施加总排序。

Comparator.compare

比较两个参数的顺序。当第一个参数小于、等于或大于第二个参数时，返回负整数、零或正整数。

查看相关的 lambda 表达式，我们可以计算出发生的比较：

(a, b) -> Integer.bitCount(a) == Integer.bitCount(b)
        ? a - b
        : Integer.bitCount(a) - Integer.bitCount(b)

这将具有较大位计数（1 位的数量）的元素视为大于具有较小位计数的元素。如果两个元素具有相同的位数，则将较大的元素视为大于较小的元素。尽管在将非常大的

Integer

值与非常小的

Integer

值进行比较时，此实现会出现问题（例如，它将

Integer.MIN_VALUE

视为大于

Integer.MAX_VALUE

）。

抛开极端数字问题不谈，这是有效的，因为如果

a - b

则

a > b

将为正，如果

a < b

则为负，如果

a == b

则为 0。 （由于溢出，这并不总是适用于极值）。根据

compareTo

，这意味着较大的数字比较小的数字被视为更大。

在表达式的上下文中，首先检查值以查看它们是否具有相同的位数 (

Integer.bitCount(a) - Integer.bitCount(b)

)，如果不同，则将较大的位数视为大于较小的位数 (

Integer.bitCount(a) - Integer.bitCount(b)

) ）。如果它们确实具有相同的位数，则将两者中较大的一个视为大于较小的 (

a - b

)。需要这个平局断路器，因为否则例如1 和 3 将被视为相等，并且排序时两者之间的顺序是任意的。

简化使用

Comparator.comparing

与此

Comparator

更简单的等效项也可以正确处理极端数字：

Comparator.comparing(Integer::bitCount)
        .thenComparing(Comparator.naturalOrder())

这使用

Comparator.comparing

和

Comparator.thenComparing

首先通过调用

Integer::bitCount

Function

的结果来比较数字，如果该函数为两者返回相同的值，则会通过比较基于Integer值的

自然排序

。

Comparator.comparing

：

接受一个函数，该函数从类型 Comparable

 中提取 

T 排序键，并返回按该排序键进行比较的

Comparator<T> 

。

Comparator.thenComparing

：

返回一个与另一个比较器的字典顺序比较器。如果这个

Comparator

认为两个元素相等，即

compare(a, b) == 0

，则使用

other

来确定顺序。

Answer 3

通过将其分解为步骤，使用类型化变量来显示每个步骤的结果类型，可以更轻松地将其可视化：

IntStream intStream = Arrays.stream(arr);
Stream<Integer> integerStream = intStream.boxed();
Stream<Integer> sortedIntegerStream = integerStream.sorted((a, b) -> 
        Integer.bitCount(a) == Integer.bitCount(b)
                ? a - b
                : Integer.bitCount(a) - Integer.bitCount(b));
IntStream sortedIntStream = sortedIntegerStream.mapToInt(Integer::intValue);
int[] sortedIntArray = sortedIntStream.toArray();
return sortedIntArray;

1. 使用 int[] 将 IntStream

    转换为 

   IntStream.stream(int[] array)。
2. 使用 IntStream 将流从

   int

   的

   Stream

   基元装箱到 Integer

    的 

   IntStream.boxed() 对象。
3. 使用

   Stream.sorted(Comparator comparator)

   根据给定的比较器对流进行排序。这个特定比较器如何工作的细节足以成为它自己的答案，但简而言之，它首先通过元素的位数（即 1 位的数量）来比较元素，如果元素具有相同的位数，则比较元素本身。所以 7 > 8（因为 7 有三个 1 位，但 8 有一个 1 位），16 > 8（两者都有一个 1 位，并且 16 > 8）。
4. 使用 Stream<Integer> 将流从 IntStream

    拆箱回到 

   Stream.mapToInt(ToIntFunction mapper)。这使用

   Integer.intValue()

   作为映射函数，它只是将

   Integer

   转换为等效的

   int

   。结果是与排序的

   IntStream

   相同的

   Stream<Integer>

   ，只不过元素是原始

   int

   值而不是

   Integer

   对象。
5. 使用 IntStream 将 int[]

    转换为包含其元素的 

   IntStream.toArray()。