本章包括 30 个问题，涉及数组、集合和几个数据结构。其目的是为在广泛的应用中遇到的一类问题提供解决方案，包括排序、查找、比较、排序、反转、填充、合并、复制和替换。提供的解决方案是用 Java8-12 实现的，它们也可以作为解决其他相关问题的基础。在本章的最后，您将掌握广泛的知识，这些知识对于解决涉及数组、集合和数据结构的各种问题非常有用。
问题
使用以下问题测试基于数组、集合和数据结构的编程能力。我强烈建议您在使用解决方案和下载示例程序之前，先尝试一下每个问题：
数组排序：编写几个程序，举例说明数组的不同排序算法。另外，编写一个数组洗牌程序。
寻找数组中的元素：编写几个程序，举例说明如何在给定的数组中找到给定的元素（原始类型和对象）。查找索引和/或简单地检查值是否在数组中。
检查两个数组是否相等或不匹配：编写一个程序，检查给定的两个数组是否相等或不匹配。
按字典比较两个数组：编写一个程序，按字典法比较给定的数组。
从数组创建流：编写从给定数组创建流的程序。
数组的最小值、最大值和平均值：编写一个程序，计算给定数组的最大值、最小值和平均值。
反转数组：写一个程序反转给定的数组。
填充和设置数组：写几个填充数组和基于生成函数设置所有元素的例子来计算每个元素。
下一个较大的元素（NGE）：编写一个程序，返回数组中每个元素的 NGE。
改变数组大小：编写一个程序，通过将数组的大小增加一个元素来增加数组的大小。另外，编写一个程序，用给定的长度增加数组的大小。
创建不可修改/不可变集合：编写几个创建不可修改和不可变集合的示例。
映射的默认值：编写一个程序，从Map获取一个值或一个默认值。
计算Map中的键是否缺失/存在：编写一个程序，计算缺失键的值或当前键的新值。
从Map中删除条目：编写一个程序，用给定的键从Map删除。
替换Map中的条目：编写一个程序来替换Map中给定的条目。
比较两个映射：编写一个比较两幅映射的程序。
合并两个映射：编写一个程序，合并两个给定的映射。
复制HashMap：编写一个程序，执行HashMap的浅复制和深复制。
排序Map：编写一个程序对Map进行排序。
删除集合中与谓词匹配的所有元素：编写一个程序，删除集合中与给定谓词匹配的所有元素。
将集合转换成数组：编写一个程序，将集合转换成数组。
过滤List集合：写几个List过滤集合的方案。揭示最好的方法。
替换List的元素：编写一个程序，将List的每个元素替换为对其应用给定运算符的结果。
线程安全集合、栈和队列：编写几个程序来举例说明 Java 线程安全集合的用法。
广度优先搜索（BFS）：编写实现 BFS 算法的程序。
Trie：编写一个实现 Trie 数据结构的程序。
元组：编写实现元组数据结构的程序。
并查：编写实现并查算法的程序。
Fenwick 树或二叉索引树：编写一个实现 Fenwick 树算法的程序。
布隆过滤器：编写实现布隆过滤器算法的程序。
**# 解决方案
以下各节介绍上述问题的解决方案。记住，通常没有一个正确的方法来解决一个特定的问题。另外，请记住，这里显示的解释仅包括解决问题所需的最有趣和最重要的细节。下载示例解决方案以查看更多详细信息，并在这个页面中试用程序。
99 排序数组
排序数组是许多域/应用中遇到的常见任务。Java 提供了一个内置的解决方案，使用比较器对原始类型和对象的数组进行排序，这一点非常常见。这种解决方案效果很好，在大多数情况下都是比较可取的方法。让我们在下一节中看看不同的解决方案。
JDK 内置解决方案
内置的解决方案名为sort()，它在java.util.Arrays类中有许多不同的风格（15 种以上的风格）。
在sort()方法的背后，有一个性能良好的快速排序类型的排序算法，称为双轴快速排序。
假设我们需要按自然顺序对整数数组进行排序（原始类型int。为此，我们可以依赖于Arrays.sort(int[] a)，如下例所示：
int[] integers = new int[]{...}; Arrays.sort(integers);
有时，我们需要对一个对象数组进行排序。假设我们有一个类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 omitted for brevity }
Melon的数组可以通过适当的Comparator按升序权重排序：
Melon[] melons = new Melon[] { ... }; Arrays.sort(melons, new Comparator<Melon>() { @Override public int compare(Melon melon1, Melon melon2) { return Integer.compare(melon1.getWeight(), melon2.getWeight()); } });
通过 Lambda 表达式重写前面的代码可以获得相同的结果：
Arrays.sort(melons, (Melon melon1, Melon melon2) -> Integer.compare(melon1.getWeight(), melon2.getWeight()));
此外，数组提供了一种并行排序元素的方法parallelSort()。幕后使用的排序算法是一种基于ForkJoinPool的并行排序合并，它将数组分解为子数组，子数组本身进行排序，然后进行合并。举个例子：
Arrays.parallelSort(melons, new Comparator<Melon>() { @Override public int compare(Melon melon1, Melon melon2) { return Integer.compare(melon1.getWeight(), melon2.getWeight()); } });
或者，通过 Lambda 表达式，我们有以下示例：
Arrays.parallelSort(melons, (Melon melon1, Melon melon2) -> Integer.compare(melon1.getWeight(), melon2.getWeight()));
前面的示例按升序对数组排序，但有时需要按降序对其排序。当我们对一个Object数组进行排序并依赖于一个Comparator时，我们可以简单地将返回的结果乘以Integer.compare()再乘以 -1：
Arrays.sort(melons, new Comparator<Melon>() { @Override public int compare(Melon melon1, Melon melon2) { return (-1) * Integer.compare(melon1.getWeight(), melon2.getWeight()); } });
或者，我们可以简单地在compare()方法中切换参数。
对于装箱原始类型的数组，解决方案可以依赖于Collections.reverse()方法，如下例所示：
Integer[] integers = new Integer[] {3, 1, 5}; // 1, 3, 5 Arrays.sort(integers); // 5, 3, 1 Arrays.sort(integers, Collections.reverseOrder());
不幸的是，没有内置的解决方案来按降序排列原始类型数组。最常见的情况是，如果我们仍然要依赖于Arrays.sort()，那么这个问题的解决方案是在数组按升序排序后反转数组（O(n)）：
// sort ascending Arrays.sort(integers); // reverse array to obtain it in descending order for (int leftHead = 0, rightHead = integers.length - 1; leftHead < rightHead; leftHead++, rightHead--) { int elem = integers[leftHead]; integers[leftHead] = integers[rightHead]; integers[rightHead] = elem; }
另一个解决方案可以依赖于 Java8 函数式风格和装箱（请注意装箱是一个非常耗时的操作）：
int[] descIntegers = Arrays.stream(integers) .boxed() //or .mapToObj(i -> i) .sorted((i1, i2) -> Integer.compare(i2, i1)) .mapToInt(Integer::intValue) .toArray();
其他排序算法
嗯，还有很多其他的排序算法。每种方法都有优缺点，最好的选择方法是对应用特定的情况进行基准测试。
让我们研究其中的一些，如下一节中强调的，从一个非常慢的算法开始。
冒泡排序
冒泡排序是一个简单的算法，基本上气泡数组的元素。这意味着它会多次遍历数组，并在相邻元素顺序错误时交换它们，如下图所示：
时间复杂度情况如下：最佳情况O(n)、平均情况O(n<sup>2</sup>)、最坏情况O(n<sup>2</sup>)
空间复杂度情况如下：最坏情况O(1)
实现冒泡排序的实用方法如下：
public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
还有一个依赖于while循环的优化版本。你可以在捆绑到这本书的代码中找到它，名字是bubbleSortOptimized()。
作为时间执行的性能比较，对于 100000 个整数的随机数组，优化后的版本将快 2 秒左右。
前面的实现可以很好地对原始类型数组进行排序，但是，要对Object数组进行排序，我们需要在代码中引入Comparator，如下所示：
public static <T> void bubbleSortWithComparator( T arr[], Comparator<? super T> c) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (c.compare(arr[j], arr[j + 1]) > 0) { T temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
还记得以前的类吗？好吧，我们可以通过实现Comparator接口为它写一个Comparator：
public class MelonComparator implements Comparator<Melon> { @Override public int compare(Melon o1, Melon o2) { return o1.getType().compareTo(o2.getType()); } }
或者，在 Java8 函数式风格中，我们有以下内容：
// Ascending Comparator<Melon> byType = Comparator.comparing(Melon::getType); // Descending Comparator<Melon> byType = Comparator.comparing(Melon::getType).reversed();
在一个名为ArraySorts的工具类中，有一个Melon数组、前面的Comparator数组和bubbleSortWithComparator()方法，我们可以按照下面的思路编写一些东西：
Melon[] melons = {...}; ArraySorts.bubbleSortWithComparator(melons, byType);
为简洁起见，跳过了带有Comparator的冒泡排序优化版本，但它在绑定到本书的代码中可用。
当数组几乎已排序时，冒泡排序速度很快。此外，它还非常适合对兔子（接近数组开头的大元素）和海龟（接近数组结尾的小元素）进行排序。但总的来说，这是一个缓慢的算法。
插入排序
插入排序算法依赖于一个简单的流。它从第二个元素开始，并将其与前面的元素进行比较。如果前面的元素大于当前元素，则算法将交换这些元素。此过程将继续，直到前面的元素小于当前元素。
在这种情况下，算法将传递到数组中的下一个元素并重复该流，如下图所示：
时间复杂度情况如下：最佳情况O(n)、平均情况O(n<sup>2</sup>)、最坏情况O(n<sup>2</sup>)
空间复杂度情况如下：最坏情况O(1)
基于此流程，原始类型的实现如下所示：
public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } }
为了比较一个Melon数组，我们需要在实现中引入一个Comparator，如下所示：
public static <T> void insertionSortWithComparator( T arr[], Comparator<? super T> c) { int n = arr.length; for (int i = 1; i < n; ++i) { T key = arr[i]; int j = i - 1; while (j >= 0 && c.compare(arr[j], key) > 0) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } }
在这里，我们有一个Comparator，它使用thenComparing()方法，按照 Java8 函数式编写的类型和重量对西瓜进行排序：
Comparator<Melon> byType = Comparator.comparing(Melon::getType) .thenComparing(Melon::getWeight);
在一个名为ArraySorts的实用类中，有一个Melon数组、前面的Comparator数组和insertionSortWithComparator()方法，我们可以编写如下内容：
Melon[] melons = {...}; ArraySorts.insertionSortWithComparator(melons, byType);
对于较小且大部分排序的数组，这可能会很快。此外，在向数组中添加新元素时，它的性能也很好。它也是非常有效的内存，因为一个单一的元素是移动。
计数排序
计数排序流从计算数组中的最小和最大元素开始。该算法根据计算出的最小值和最大值定义一个新的数组，该数组将使用元素作为索引对未排序的元素进行计数。此外，以这样的方式修改这个新数组，使得每个索引处的每个元素存储先前计数的总和。最后，从这个新的数组中得到排序后的数组。
时间复杂度情况如下：最佳情况O(n + k)、平均情况O(n + k)、最坏情况O(n + k)
空间复杂度情况如下：最坏情况O(k)
k is the number of possible values in the range.
n is the number of elements to be sorted.
让我们考虑一个简单的例子。初始数组包含以下元素，arr：4、2、6、2、6、8、5：
最小元件为2，最大元件为8。新数组counts的大小等于最大值减去最小值+1=8-2+1=7。
对每个元素进行计数将产生以下数组（counts[arr[i] - min]++）：
counts[2] = 1 (4); counts[0] = 2 (2); counts[4] = 2 (6); counts[6] = 1 (8); counts[3] = 1 (5);
现在，我们必须循环此数组，并使用它重建排序后的数组，如下所示：
public static void countingSort(int[] arr) { int min = arr[0]; int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] < min) { min = arr[i]; } else if (arr[i] > max) { max = arr[i]; } } int[] counts = new int[max - min + 1]; for (int i = 0; i < arr.length; i++) { counts[arr[i] - min]++; } int sortedIndex = 0; for (int i = 0; i < counts.length; i++) { while (counts[i] > 0) { arr[sortedIndex++] = i + min; counts[i]--; } } }
这是一个非常快速的算法。
堆排序
堆排序是一种依赖于二进制堆（完全二叉树）的算法。
时间复杂度情况如下：最佳情况O(n log n)、平均情况O(n log n)、最坏情况O(n log n)
空间复杂度情况如下：最坏情况O(1)
可以通过最大堆（父节点总是大于或等于子节点）按升序排序元素，通过最小堆（父节点总是小于或等于子节点）按降序排序元素。
在第一步，该算法使用提供的数组来构建这个堆，并将其转换为一个最大堆（该堆由另一个数组表示）。因为这是一个最大堆，所以最大的元素是堆的根。在下一步中，根与堆中的最后一个元素交换，堆大小减少 1（从堆中删除最后一个节点）。堆顶部的元素按顺序排列。最后一步由建堆（以自顶向下的方式构建堆的递归过程）和堆的根（重构最大堆）组成。重复这三个步骤，直到堆大小大于 1：
例如，假设上图中的数组-4、5、2、7、1：
因此，在第一步，我们构建堆：4、5、2、7、1。
我们构建了最大堆：7、5、2、4、1（我们将5与4、4与7、5与7进行了交换）。
接下来，我们将根（7）与最后一个元素（1）交换并删除7。结果：1、5、2、4、7。
进一步，我们再次构建最大堆：5、4、2、1（我们将5与1进行了交换，将1与4进行了交换）。
我们将根（5）与最后一个元素（1）交换，并删除5。结果：1、4、2、5、7。
接下来，我们再次构建最大堆：4、1、2（我们将1与4进行了交换）。
我们将根（4）与最后一个元素（2）交换，并删除4。结果：2、1。
这是一个最大堆，因此将根（2）与最后一个元素（1）交换并移除2：1、2、4、5、7。
完成！堆中只剩下一个元素（1）。
在代码行中，前面的示例可以概括如下：
public static void heapSort(int[] arr) { int n = arr.length; buildHeap(arr, n); while (n > 1) { swap(arr, 0, n - 1); n--; heapify(arr, n, 0); } } private static void buildHeap(int[] arr, int n) { for (int i = arr.length / 2; i >= 0; i--) { heapify(arr, n, i); } } private static void heapify(int[] arr, int n, int i) { int left = i * 2 + 1; int right = i * 2 + 2; int greater; if (left < n && arr[left] > arr[i]) { greater = left; } else { greater = i; } if (right < n && arr[right] > arr[greater]) { greater = right; } if (greater != i) { swap(arr, i, greater); heapify(arr, n, greater); } } private static void swap(int[] arr, int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; }
如果我们想要比较对象，那么我们必须在实现中引入一个Comparator。此解决方案在捆绑到本书的代码中以heapSortWithComparator()的名称提供。
这里是一个用 Java8 函数式编写的Comparator，它使用thenComparing()和reversed()方法按类型和重量降序排列瓜类：
Comparator<Melon> byType = Comparator.comparing(Melon::getType) .thenComparing(Melon::getWeight).reversed();
在一个名为ArraySorts的实用类中，有一个Melon数组、前面的Comparator数组和heapSortWithComparator()方法，我们可以编写如下内容：
Melon[] melons = {...}; ArraySorts.heapSortWithComparator(melons, byType);
堆排序相当快，但不稳定。例如，对已排序的数组进行排序可能会使其保持不同的顺序。
我们将在这里停止关于排序数组的论文，但是，在本书附带的代码中，还有一些排序算法可用：
还有许多其他算法专门用于排序数组。其中一些是建立在这里介绍的基础上的（例如，梳排序、鸡尾酒排序和奇偶排序是冒泡排序的风格，桶排序是通常依赖于插入排序的分布排序，基数排序（LSD）是类似于桶排序的稳定分布，Gnome 排序是插入排序的变体）。
其他则是不同的方法（例如，Arrays.sort()方法实现的快速排序，Arrays.parallelSort()方法实现的合并排序）。
作为对本节的奖励，让我们看看如何洗牌一个数组。实现这一点的有效方法依赖于 Fisher-Yates 洗牌（称为 Knuth 洗牌）。基本上，我们以相反的顺序循环数组，然后随机交换元素。对于原始类型（例如，int），实现如下：
public static void shuffleInt(int[] arr) { int index; Random random = new Random(); for (int i = arr.length - 1; i > 0; i--) { index = random.nextInt(i + 1); swap(arr, index, i); } }
在绑定到本书的代码中，还有一个实现，用于对Object的数组进行洗牌。
通过Collections.shuffle(List<?> list)洗牌列表非常简单。
