100 在数组中查找元素

当我们在数组中搜索一个元素时，我们可能感兴趣的是找出这个元素出现的索引，或者只找出它是否存在于数组中。本节介绍的解决方案具体化为以下屏幕截图中的方法：

让我们在下一节中看看不同的解决方案。

只检查是否存在

假设以下整数数组：

int[] numbers = {4, 5, 1, 3, 7, 4, 1};

由于这是一个原始类型数组，解决方案可以简单地循环数组并返回给定整数的第一个匹配项，如下所示：

public static boolean containsElement(int[] arr, int toContain) {
  for (int elem: arr) {
    if (elem == toContain) {
      return true;
    }
  }
  return false;
}

这个问题的另一个解决方法可以依赖于Arrays.binarySearch()方法。这种方法有几种风格，但在这种情况下，我们需要这个：int binarySearch(int[] a, int key)。该方法将搜索给定数组中的给定键，并返回相应的索引或负值。唯一的问题是，此方法仅适用于已排序的数组；因此，我们需要事先对数组排序：

public static boolean containsElement(int[] arr, int toContain) {
  Arrays.sort(arr);
  int index = Arrays.binarySearch(arr, toContain);
  return (index >= 0);
}

如果数组已经排序，那么可以通过删除排序步骤来优化前面的方法。此外，如果数组被排序，前面的方法可以返回数组中元素出现的索引，而不是一个boolean。但是，如果数组没有排序，请记住返回的索引对应于排序的数组，而不是未排序的（初始）数组。如果不想对初始数组进行排序，则建议将数组的克隆传递给此方法。另一种方法是在这个辅助方法中克隆数组。

在 Java8 中，解决方案可以依赖于函数式方法。这里一个很好的候选者是anyMatch()方法。此方法返回流中是否有元素与提供的谓词匹配。因此，我们需要做的就是将数组转换为流，如下所示：

public static boolean containsElement(int[] arr, int toContain) {
  return Arrays.stream(arr)
    .anyMatch(e -> e == toContain);
}

对于任何其他原始类型，改编或概括前面的示例都非常简单。

现在，让我们集中精力在数组中寻找Object。让我们考虑一下Melon类：

public class Melon {
  private final String type;
  private final int weight;
  // constructor, getters, equals() and hashCode() skipped for brevity
}

接下来，让我们考虑一个Melon数组：

Melon[] melons = new Melon[] {new Melon("Crenshaw", 2000),
  new Melon("Gac", 1200), new Melon("Bitter", 2200)
};

现在，假设我们要在这个数组中找到 1200 克的木瓜。一个解决方案可以依赖于equals()方法，该方法用于确定两个对象的相等性：

public static <T> boolean 
    containsElementObject(T[] arr, T toContain) {
  for (T elem: arr) {
    if (elem.equals(toContain)) {
      return true;
    }
  }
  return false;
}

同样，我们可以依赖于Arrays.asList(arr).contains(find)。基本上，将数组转换为一个List并调用contains()方法。在幕后，这种方法使用的是equals()合同。

如果此方法存在于名为ArraySearch的工具类中，则以下调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Gac", 1200));

只要我们想依赖equals()合同，这个解决方案就行。但是我们可以认为，如果甜瓜的名字出现（Gac），或者它的重量出现（1200），那么我们的甜瓜就存在于数组中。对于这种情况，更实际的做法是依赖于Comparator：

public static <T> boolean containsElementObject(
    T[] arr, T toContain, Comparator<? super T> c) {
  for (T elem: arr) {
    if (c.compare(elem, toContain) == 0) {
      return true;
    }
  }
  return false;
}

现在，一个只考虑瓜的类型的Comparator可以写为：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);

由于Comparator忽略了瓜的重量（没有 1205 克的瓜），下面的调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Gac", 1205), byType);

另一种方法依赖于binarySearch()的另一种风格。Arrays类提供了一个binarySearch()方法，该方法获取一个Comparator、<T> int binarySearch(T[] a, T key, Comparator<? super T> c)。这意味着我们可以如下使用它：

public static <T> boolean containsElementObject(
    T[] arr, T toContain, Comparator<? super T> c) {
  Arrays.sort(arr, c);
  int index = Arrays.binarySearch(arr, toContain, c);
  return (index >= 0);
}

如果初始数组状态应保持不变，则建议将数组的克隆传递给此方法。另一种方法是在这个辅助方法中克隆数组。

现在，一个只考虑瓜重的Comparator可以写为：

Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);

由于Comparator忽略了甜瓜的类型（没有蜜瓜类型的甜瓜），下面的调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Honeydew", 1200), byWeight);

只检查第一个索引

对于一组原始类型，最简单的实现就说明了这一点：

public static int findIndexOfElement(int[] arr, int toFind) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == toFind) {
      return i;
    }
  }
  return -1;
}

依靠 Java8 函数风格，我们可以尝试循环数组并过滤与给定元素匹配的元素。最后，只需返回找到的第一个元素：

public static int findIndexOfElement(int[] arr, int toFind) {
  return IntStream.range(0, arr.length)
    .filter(i -> toFind == arr[i])
    .findFirst()
    .orElse(-1);
}

对于Object数组，至少有三种方法。首先，我们可以依据equals()合同：

public static <T> int findIndexOfElementObject(T[] arr, T toFind) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i].equals(toFind)) {
      return i;
    }
  }
  return -1;
}

同样，我们可以依赖于Arrays.asList(arr).indexOf(find)。基本上，将数组转换为一个List并调用indexOf()方法。在幕后，这种方法使用的是equals()合同。

其次，我们可以依赖于Comparator：

public static <T> int findIndexOfElementObject(
    T[] arr, T toFind, Comparator<? super T> c) {
  for (int i = 0; i < arr.length; i++) {
    if (c.compare(arr[i], toFind) == 0) {
      return i;
    }
  }
  return -1;
}

第三，我们可以依赖 Java8 函数式风格和一个Comparator：

public static <T> int findIndexOfElementObject(
    T[] arr, T toFind, Comparator<? super T> c) {
  return IntStream.range(0, arr.length)
    .filter(i -> c.compare(toFind, arr[i]) == 0)
    .findFirst()
    .orElse(-1);
}

101 检查两个数组是否相等或不匹配

如果两个原始数组包含相同数量的元素，则它们相等，并且两个数组中所有对应的元素对都相等

这两个问题的解决依赖于Arrays实用类。下面几节给出了解决这些问题的方法。

检查两个数组是否相等

通过Arrays.equals()方法可以很容易地检查两个数组是否相等。对于基本类型、Object和泛型，这个标志方法有很多种风格。它还支持比较器。

让我们考虑以下三个整数数组：

int[] integers1 = {3, 4, 5, 6, 1, 5};
int[] integers2 = {3, 4, 5, 6, 1, 5};
int[] integers3 = {3, 4, 5, 6, 1, 3};

现在，让我们检查一下integers1是否等于integers2，以及integers1是否等于integers3。这很简单：

boolean i12 = Arrays.equals(integers1, integers2); // true
boolean i13 = Arrays.equals(integers1, integers3); // false

前面的例子检查两个数组是否相等，但是我们也可以通过boolean equals(int[] a, int aFromIndex, int aToIndex, int[] b, int bFromIndex, int bToIndex)方法检查数组的两个段（或范围）是否相等。因此，我们通过范围[aFromIndex, aToIndex)来划分第一个数组的段，通过范围[bFromIndex, bToIndex)来划分第二个数组的段：

// true
boolean is13 = Arrays.equals(integers1, 1, 4, integers3, 1, 4);

现在，让我们假设Melon的三个数组：

public class Melon {
  private final String type;
  private final int weight;
  public Melon(String type, int weight) {
    this.type = type;
    this.weight = weight;
  }
  // getters, equals() and hashCode() omitted for brevity
}
Melon[] melons1 = {
  new Melon("Horned", 1500), new Melon("Gac", 1000)
};
Melon[] melons2 = {
  new Melon("Horned", 1500), new Melon("Gac", 1000)
};
Melon[] melons3 = {
  new Melon("Hami", 1500), new Melon("Gac", 1000)
};

基于equals()合同或基于指定的Comparator，两个Object数组被视为相等。我们可以很容易地检查melons1是否等于melons2，以及melons1是否等于melons3，如下所示：

boolean m12 = Arrays.equals(melons1, melons2); // true
boolean m13 = Arrays.equals(melons1, melons3); // false

在明确的范围内，使用boolean equals(Object[] a, int aFromIndex, int aToIndex, Object[] b, int bFromIndex, int bToIndex)：

boolean ms13 = Arrays.equals(melons1, 1, 2, melons3, 1, 2); // false

虽然这些示例依赖于Melon.equals()实现，但以下两个示例依赖于以下两个Comparator：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);
Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);

使用布尔值equals(T[] a, T[] a2, Comparator<? super T> cmp)，我们得到以下结果：

boolean mw13 = Arrays.equals(melons1, melons3, byWeight); // true
boolean mt13 = Arrays.equals(melons1, melons3, byType);   // false

并且，在显式范围内，使用Comparator、<T> boolean equals(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)，我们得到：

// true
boolean mrt13 = Arrays.equals(melons1, 1, 2, melons3, 1, 2, byType);

检查两个数组是否包含不匹配项

如果两个数组相等，则不匹配应返回 -1。但是如果两个数组不相等，那么不匹配应该返回两个给定数组之间第一个不匹配的索引。为了解决这个问题，我们可以依赖 JDK9Arrays.mismatch()方法。

例如，我们可以检查integers1和integers2之间的不匹配，如下所示：

int mi12 = Arrays.mismatch(integers1, integers2); // -1

结果是 -1，因为integers1和integers2相等。但是如果我们检查integers1和integers3，我们会得到值 5，这是这两个值之间第一个不匹配的索引：

int mi13 = Arrays.mismatch(integers1, integers3); // 5

如果给定的数组有不同的长度，而较小的数组是较大数组的前缀，那么返回的不匹配就是较小数组的长度。

对于Object的数组，也有专用的mismatch()方法。这些方法依赖于equals()合同或给定的Comparator。我们可以检查melons1和melons2之间是否存在不匹配，如下所示：

int mm12 = Arrays.mismatch(melons1, melons2); // -1

如果第一个索引发生不匹配，则返回值为 0。这在melons1和melons3的情况下发生：

int mm13 = Arrays.mismatch(melons1, melons3); // 0

在Arrays.equals()的情况下，我们可以使用Comparator检查显式范围内的不匹配：

// range [1, 2), return -1
int mms13 = Arrays.mismatch(melons1, 1, 2, melons3, 1, 2);
// Comparator by melon's weights, return -1
int mmw13 = Arrays.mismatch(melons1, melons3, byWeight);
// Comparator by melon's types, return 0
int mmt13 = Arrays.mismatch(melons1, melons3, byType);
// range [1,2) and Comparator by melon's types, return -1
int mmrt13 = Arrays.mismatch(melons1, 1, 2, melons3, 1, 2, byType);

102 按字典顺序比较两个数组

从 JDK9 开始，我们可以通过Arrays.compare()方法按字典顺序比较两个数组。既然不需要重新发明轮子，那么就升级到 JDK9，让我们深入研究一下。

两个数组的词典比较可能返回以下结果：

   0，如果给定数组相等并且包含相同顺序的相同元素

   如果第一个数组按字典顺序小于第二个数组，则值小于 0

   如果第一个数组按字典顺序大于第二个数组，则该值大于 0

如果第一个数组的长度小于第二个数组的长度，则第一个数组在词典上小于第二个数组。如果数组具有相同的长度，包含原始类型，并且共享一个共同的前缀，那么字典比较就是比较两个元素的结果，精确地说就是Integer.compare(int, int)、Boolean.compare(boolean, boolean)、Byte.compare(byte, byte)等等。如果数组包含Object，那么字典比较依赖于给定的Comparator或Comparable实现。

首先，让我们考虑以下原始类型数组：

int[] integers1 = {3, 4, 5, 6, 1, 5};
int[] integers2 = {3, 4, 5, 6, 1, 5};
int[] integers3 = {3, 4, 5, 6, 1, 3};

现在，integers1在词典上等于integers2，因为它们相等并且包含相同顺序的相同元素，int compare(int[] a, int[] b)：

int i12 = Arrays.compare(integers1, integers2); // 0

但是，integers1在字典上大于integers3，因为它们共享相同的前缀（3，4，5，6，1），但是对于最后一个元素，Integer.compare(5,3)返回一个大于 0 的值，因为 5 大于 3：

int i13 = Arrays.compare(integers1, integers3); // 1

可以在不同的数组范围内进行词典比较。例如，下面的示例通过int compare(int[] a, int aFromIndex, int aToIndex, int[] b, int bFromIndex, int bToIndex)方法比较范围[3, 6]中的integers1和integers3：

int is13 = Arrays.compare(integers1, 3, 6, integers3, 3, 6); // 1

对于Object的数组，Arrays类还提供了一组专用的compare()方法。还记得Melon类吗？好吧，为了比较两个没有显式Comparator的Melon数组，我们需要实现Comparable接口和compareTo()方法。假设我们依赖于瓜的重量，如下所示：

public class Melon implements Comparable {
  private final String type;
  private final int weight;
  @Override
  public int compareTo(Object o) {
    Melon m = (Melon) o;
    return Integer.compare(this.getWeight(), m.getWeight());
  }
  // constructor, getters, equals() and hashCode() omitted for brevity
}

注意，Object数组的词典比较不依赖于equals()。它需要显式的Comparator或Comparable元素。

假设Melon的以下数组：

Melon[] melons1 = {new Melon("Horned", 1500), new Melon("Gac", 1000)};
Melon[] melons2 = {new Melon("Horned", 1500), new Melon("Gac", 1000)};
Melon[] melons3 = {new Melon("Hami", 1600), new Melon("Gac", 800)};

让我们通过<T extends Comparable<? super T>> int compare(T[] a, T[] b)将melons1与melons2进行词汇对比：

int m12 = Arrays.compare(melons1, melons2); // 0

因为melons1和melons2是相同的，所以结果是 0。

现在，让我们对melons1和melons3做同样的事情。这一次，结果将是否定的，这意味着在词典中，melons1小于melons3。这是真的，因为在指数 0 时，角瓜的重量是 1500 克，比哈密瓜的重量要轻，哈密瓜的重量是 1600 克：

int m13 = Arrays.compare(melons1, melons3); // -1

我们可以通过<T extends Comparable<? super T>> int compare(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex)方法在数组的不同范围内进行比较。例如，在公共范围[1, 2]中，melons1在字典上大于melons2，因为 Gac 的重量在melons1中为 1000g，在melons3中为 800g：

int ms13 = Arrays.compare(melons1, 1, 2, melons3, 1, 2); // 1

如果我们不想依赖Comparable元素（实现Comparable，我们可以通过<T> int compare(T[] a, T[] b, Comparator<? super T> cmp)方法传入一个Comparator：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);
int mt13 = Arrays.compare(melons1, melons3, byType); // 14

也可以通过<T> int compare(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)使用范围：

int mrt13 = Arrays.compare(melons1, 1, 2, melons3, 1, 2, byType); // 0

如果数字数组应该被无符号处理，那么依赖于一堆Arrays.compareUnsigned()方法，这些方法可用于byte、short、int和long。

根据String.compareTo()和int compareTo(String anotherString)按字典顺序比较两个字符串。

103 从数组创建流

一旦我们从一个数组中创建了一个Stream，我们就可以访问所有流 API。因此，这是一个方便的操作，这是很重要的，在我们的工具带。

让我们从字符串数组开始（也可以是其他对象）：

String[] arr = {"One", "Two", "Three", "Four", "Five"};

从这个String[]数组创建Stream最简单的方法是依赖于从 JDK8 开始的Arrays.stream()方法：

Stream<String> stream = Arrays.stream(arr);

或者，如果我们需要来自子数组的流，那么只需添加范围作为参数。例如，让我们从(0, 2)之间的元素创建一个Stream，即 1 到 2：

Stream<String> stream = Arrays.stream(arr, 0, 2);

同样的情况，但通过一个List可以写为：

Stream<String> stream = Arrays.asList(arr).stream();
Stream<String> stream = Arrays.asList(arr).subList(0, 2).stream();

另一种解决方案依赖于Stream.of()方法，如以下简单示例所示：

Stream<String> stream = Stream.of(arr);
Stream<String> stream = Stream.of("One", "Two", "Three");

从Stream创建数组可以通过Stream.toArray()方法完成。例如，一个简单的方法如下所示：

String[] array = stream.toArray(String[]::new);

另外，让我们考虑一个原始数组：

int[] integers = {2, 3, 4, 1};

在这种情况下，Arrays.stream()方法可以再次提供帮助，唯一的区别是返回的结果是IntStream类型（这是Stream的int原始类型特化）：

IntStream intStream = Arrays.stream(integers);

但是IntStream类还提供了一个of()方法，可以如下使用：

IntStream intStream = IntStream.of(integers);

有时，我们需要定义一个增量步长为 1 的有序整数的Stream。此外，Stream的大小应该等于数组的大小。特别是对于这种情况，IntStream方法提供了两种方法range(int inclusive, int exclusive)和rangeClosed(int startInclusive, int endInclusive)：

IntStream intStream = IntStream.range(0, integers.length);
IntStream intStream = IntStream.rangeClosed(0, integers.length);

从整数的Stream创建数组可以通过Stream.toArray()方法完成。例如，一个简单的方法如下所示：

int[] intArray = intStream.toArray();
// for boxed integers
int[] intArray = intStream.mapToInt(i -> i).toArray();

除了流的IntStream特化之外，JDK8 还提供long（LongStream）和double（DoubleStream）的特化。

104 数组的最小值、最大值和平均值

计算数组的最小值、最大值和平均值是一项常见的任务。让我们看看在函数式和命令式编程中解决这个问题的几种方法。

计算最大值和最小值

计算数字数组的最大值可以通过循环数组并通过与数组的每个元素进行比较来跟踪最大值来实现。就代码行而言，可以编写如下：

public static int max(int[] arr) {
  int max = arr[0];
  for (int elem: arr) {
    if (elem > max) {
      max = elem;
    }
  }
  return max;
}

在可读性方面，可能需要使用Math.max()方法而不是if语句：

...
max = Math.max(max, elem);
...

假设我们有以下整数数组和一个名为MathArrays的工具类，其中包含前面的方法：

int[] integers = {2, 3, 4, 1, -4, 6, 2};

该数组的最大值可以容易地获得如下：

int maxInt = MathArrays.max(integers); // 6

在 Java8 函数式风格中，此问题的解决方案需要一行代码：

int maxInt = Arrays.stream(integers).max().getAsInt();

在函数式方法中，max()方法返回一个OptionalInt。同样，我们有OptionalLong和OptionalDouble。

此外，我们假设一个对象数组，在本例中是一个Melon数组：

Melon[] melons = {
  new Melon("Horned", 1500), new Melon("Gac", 2200),
  new Melon("Hami", 1600), new Melon("Gac", 2100)
};
public class Melon implements Comparable {
  private final String type;
  private final int weight;
  @Override
  public int compareTo(Object o) {
    Melon m = (Melon) o;
    return Integer.compare(this.getWeight(), m.getWeight());
  }
  // constructor, getters, equals() and hashCode() omitted for brevity
}

很明显，我们前面定义的max()方法不能用于这种情况，但逻辑原理保持不变。这一次，实现应该依赖于Comparable或Comparator。基于Comparable的实现可以如下：

public static <T extends Comparable<T>> T max(T[] arr) {
  T max = arr[0];
  for (T elem : arr) {
    if (elem.compareTo(max) > 0) {
      max = elem;
   }
  }
  return max;
}

检查Melon.compareTo()方法，注意我们的实现将比较瓜的重量。因此，我们可以很容易地从我们的数组中找到最重的瓜，如下所示：

Melon maxMelon = MathArrays.max(melons); // Gac(2200g)

依赖于Comparator的实现可以写为：

public static <T> T max(T[] arr, Comparator<? super T> c) {
  T max = arr[0];
  for (T elem: arr) {
    if (c.compare(elem, max) > 0) {
      max = elem;
    }
  }
  return max;
}

并且，如果我们根据甜瓜的类型定义一个Comparator，我们有以下结果：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);

然后，我们得到与字符串的词典比较相一致的最大值：

Melon maxMelon = MathArrays.max(melons, byType); // Horned(1500g)

在 Java8 函数式风格中，此问题的解决方案需要一行代码：

Melon maxMelon = Arrays.stream(melons).max(byType).orElseThrow();