1.1.5 案例分析

案例1-1：数组元素的逆置

编写一个函数reverseArray()，将数组中的元素逆置。例如原数组中的元素顺序是{1，2，3，4，5}，那么逆置后数组中的元素顺序是{5，4，3，2，1}。

本题难度：★

题目分析：

数组元素的逆置操作一般要求不创建新数组，只在原数组内将数组元素的顺序颠倒过来，这样操作的效率比较高，实现起来也更加简单。

要将包含elemNumber个元素的数组进行逆置，需要定义一个临时变量tmpElem作为数据缓冲区，同时要设置变量low和high，作为数组的下标分别指向数组的第1个元素和最后一个元素。然后执行以下步骤。

（1）将low指向的元素和high指向的元素通过临时变量tmpElem交换位置。

（2）执行low++和high--，重复执行步骤（1）直到low≥high。

通过以上步骤可将一个包含elemNumber个元素的数组原地逆置。该算法的时间复杂度为O（n），空间复杂度为O（1）。该算法的Java代码描述如下。

请注意，函数reverseArray()是MyArray类的成员函数，因此该函数可直接对数组array进行操作，不需要通过参数传递进来。

下面我们通过一个测试程序来检查reverseArray()函数的正确性。

测试程序首先初始化了一个容量为5的数组，然后通过循环调用array.insertElem()函数向数组中插入元素1、2、3、4、5，再调用array.printArray()函数打印数组内容，接下来调用array.reverseArray()函数将数组元素逆置，最后再次调用array.printArray()函数打印数组内容。运行结果如图1-9所示。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-2”中获取。

案例1-2：删除数组中的重复元素

编写一个函数purge()，删除整数数组中的重复元素。例如，数组为{1，1，3，5，2，3，1，5，6，8}，删除重复元素后数组变为{1，3，5，2，6，8}。

本题难度：★★

题目分析：

本题是一道经典的数组问题，我们用三种方法求解。

要删除数组中的重复元素，最直观的方法就是先定位一个数组元素，然后从前向后扫描整个数组，如果发现与定位的元素相同的元素，就调用deleteElem()函数将该元素删除。不断调整定位的元素，直到将整个数组中重复的元素全部删除为止。该方法的Java代码描述如下。

上述代码实现了删除整型数组中重复元素的操作。在代码中，变量i指向的元素array[i]即为定位的元素，也就是数组中最终要保留的元素，然后通过变量j从元素array[i+1]开始顺序遍历，将后续的每个元素都与array[i]进行比较，一旦发现array[i]与array[j]重复，就调用deleteElem()函数将元素array[j]删除。

在函数purge()中，内层的while循环在j等于数组元素的数量elemNumber后停止，表示数组中再没有与元素array[i]重复的元素了。外层的while循环由变量i控制，表示要在数组array中删除与当前元素array[i]重复的所有元素。外层循环在i等于elemNumber后停止，此时数组中所有的重复元素都将被删除（只保留一个，删掉重复的）。

下面我们通过一个测试程序检验函数purge()的正确性。

运行结果如图1-10所示。

如图1-10所示，最初数组的内容是{1，1，3，5，2，3，1，5，6，8}，删除重复元素后数组的内容变为{1，3，5，2，6，8}，可见程序执行正确。

上述算法简单直观，但是时间复杂度很高，可达到（n3）。首先通过二重循环找出数组中存在的重复元素，这个操作的时间复杂度是O（n2）；而执行deleteElem()函数的时间复杂度是O（n），综合起来该算法的时间复杂度为O（n3）。其实该算法还存在一些优化空间。

当找到重复元素后，可以不马上调用deleteElem()函数，而是先做一个标记，这样就可以节省每次调用deleteElem()函数时批量移动数组元素的时间。当找出了全部重复元素后再进行整体删除，这样只需要执行一次二重循环找出数组中的重复元素，再加上一次循环删除重复的元素即可，时间复杂度降为O（n2）+O（n），整体的时间复杂度仍是O（n2）级别。改进后的算法描述如下。

在上述算法中，首先通过一个二重for循环找出数组中的全部重复元素，并将这些重复的元素用标记FLAG即-111覆盖。以数组{1，1，3，5，2，3，1，5，6，8}为例，经过这个二重循环处理后，其数组状态如图1-11所示。

然后执行一个一重循环，找到数组中第1个FLAG标记，并用变量i指向该数组元素，如图1-12所示。

接下来用一重for循环将FLAG标记的重复元素删除，也就是用后面的数组元素覆盖FLAG。具体做法如下。

（1）初始化变量j=i+1。

（2）用变量j扫描数组中的后续元素，如果array[j]不是FLAG，则用array[j]覆盖array[i]，然后i和j都向后移动一个位置（i++，j++）；如果array[j]是FLAG，则j++，寻找下一个非FLAG的有效值。按照这种方法用变量j扫描完整个数组后，所有FLAG都将被删除。

（3）最后还要修正elemNumber的值，因为删除数组中的重复元素后，数组元素的数量将减少。

如图1-13所示，在上面的操作过程中，变量i指向的是最终存放有效元素的位置，而变量j的作用是在数组中寻找有效元素，即未被FLAG标识的元素，并将这个有效元素的值赋给array[i]。只要经过这样一重循环操作，就可将数组中的FLAG全部删除。

下面我们通过相同的测试程序检验改进后的函数purge()的正确性，运行结果如图1-14所示。

可见改进后的算法也可以得到正确的结果。

现在我们已将算法的时间复杂度从O（n3）优化到了O（n2），还可以利用Java类库中提供的容器类HashSet来进行进一步的优化。

熟悉Java容器类的读者应当知道，HashSet是java.util包中的类，在向HashSet中添加新的对象时，HashSet会判断重复的对象。如果添加的对象与HashSet内已有对象重复则添加失败，同时返回false；如果没有重复则添加成功并返回true。向HashSet中添加元素并查重的操作的时间复杂度仅为O（1），这是因为HashSet内部封装了HashMap，其本身是一个Hash表结构。

我们可以利用HashSet的这一特性，将数组中的元素依次添加到HashSet中（调用HashSet.add()函数），如果添加成功，则说明当前添加的数组元素与HashSet中的已有元素不重复；如果添加失败，则说明当前添加的数组元素与HashSet中的已有元素有重复，且该元素就是数组中的重复元素。将找出的这些重复元素标记为FLAG，再通过一次for循环将数组中的FLAG全部删除，这样就可以删除数组中的重复元素。

不难看出，利用HashSet查找数组中重复元素的时间复杂度为O（n），将数组中的FLAG全部删除的时间复杂度也为O（n），所以整个算法的时间复杂度是O（n）+O（n），也是O（n）级别。代价就是需要一个HashSet作为辅助工具，空间复杂度要高一些。

该算法的Java代码描述如下。

使用上面提供的测试程序检验改进后的purge()，程序的运行结果如图1-15所示。

可见改进后的算法也可以得到正确的结果。

其实还有一种更简单的方法甚至不需要给原数组中的重复元素标记FLAG。因为HashSet中已保存了过滤了重复元素的数组元素，所以可以直接将HashSet中保存的数据依次读出，再更新到原数组中。但是这种方法存在一个问题，就是HashSet中的数据是无序的，所以从HashSet中读取出的元素顺序可能与原数组中的元素顺序不一致。如果不在意数组中元素的顺序而只考虑删除重复元素，那么也可以采用这种方法。本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-3”中获取。