1.2 数组的基本算法设计

1.2.1 LeetCode27——移除元素★

【问题描述】 给定一个数组nums和一个值val，请原地移除所有数值等于val的元素，并返回移除后数组的新长度。注意，不要使用额外的数组空间，仅使用 O （1）额外空间并原地修改输入数组；元素的顺序可以改变；不需要考虑数组中超出新长度后面的元素。

例如，nums=[3，2，2，3]，val=3，返回的新长度为2，并且nums中的前两个元素均为2。

【限制】 0≤nums.length≤100，0≤nums[ i ]≤50，0≤val≤100。

【解法1】 整体建表法 。为了描述简单，用 a 表示nums数组。在 a 中删除所有值为val的元素得到结果数组 b ，返回数组 b 即可。由于题目要求空间复杂度为 O （1），所以只能将 b 和 a 共享。其思路是先将结果数组 a 看成空表（初始时将表示其中元素个数的 k 置为0），用 i 从0开始遍历 a ：

（1）若 a _i ≠val，说明 a _i 是要保留的元素，将其插入 a 的末尾，即置 a _k = a _i ， k ++，如图1.6所示。

（2）若 a _i =val，说明 a _i 是要删除的元素，不需要将 a _i 重新插入，即直接跳过。

最后返回结果数组长度 k 即可。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

【解法2】 元素移动法 。用 i 从0开始遍历 a ，用 k （ k ≥0）累计到当前为止要删除的元素的个数（初始值为0）：

（1）若 a _i ≠val，说明 a _i 是要保留的元素，将 a _i 前移 k 个位置重新插入 a 中，如图1.7所示（ k =0时原地移动一次）。

（2）若 a _i =val，说明 a _i 是要删除的元素，不移动 a _i 并且执行 k ++。最后返回结果数组长度 n - k 即可。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

【解法3】 区间划分法。用 a [0.. j ]区间存放保留的元素（称为“保留元素区间”），初始时该区间为空，即 j =-1。用 i 从0开始遍历 a ，保留元素区间之后的 a [ j +1.. i -1]区间存放删除的元素（称为“删除元素区间”），初始时该区间也为空（因为 i =0）。 i 从0开始遍历 a ：

（1）若 a _i ≠val，说明 a _i 是要保留的元素，将其移动到保留元素区间的末尾，其操作是执行 j ++，将 a _i 和 a _j 交换，如图1.8所示。此时 a _i 位置的元素变成了删除元素，即将删除元素区间后移一个位置，同时保留元素区间增加了一个元素。

（2）若 a _i =val，说明 a _i 是要删除的元素，不做任何操作直接将 a _i 放置在删除元素区间的末尾。

最后返回保留元素区间的长度 j +1即可。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.2.2 LeetCode283——移动0★

【问题描述】 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非0元素的相对顺序。注意，必须在不复制数组的情况下对数组原地进行操作。

例如，nums=[0，1，0，3，12]，答案为[1，3，12，0，0]。

【限制】 1≤nums.length≤10 ⁴ ，-2 ³¹ ≤nums[ i ]≤2 ³¹ -1。

【解法1】 整体建表法 。采用1.2.1节中解法1的思路，将val看成0，删除nums中所有为0的元素，删除完毕后nums[0.. k -1]中就是所有不为0的元素，即保留的元素，再将其余部分（即nums[ k .. n -1]）全部置为0即可。

【解法2】 元素移动法 。采用1.2.1节中解法2的思路，同样将val看成0，将所有不等于0的元素移动到最前面（共有 k 个等于0的元素），这样nums[0.. n - k -1]中就是所有不为0的元素，即保留的元素，再将其余部分nums[ n - k .. n -1]全部置为0即可。

【解法3】 区间划分法 。采用1.2.1节中解法3的思路，同样将val看成0，将所有不等于0的元素移动到最前面，即nums[0.. j ]区间中，它们是保留的元素，再将后面的区间（即nums[ j +1.. n -1]）全部置为0即可。

1.2.3 LeetCode2460——对数组执行操作★

【问题描述】 给定一个下标从0开始的数组nums，数组的大小为 n ，且由非负整数组成，对数组执行 n -1步操作，其中第 i 步操作（从0开始计数）要求对nums中的第 i 个元素执行下述指令：

（1）如果nums[ i ]=nums[ i +1]，将nums[ i ]的值变成原来的2倍，nums[ i +1]的值变成0。

（2）否则跳过这步操作。

在执行完全部操作后将所有的0移动到数组的末尾，返回结果数组。注意，操作应当依次有序执行，而不是一次性全部执行。

例如，nums=[1，2，2，1，1，0]，执行如下。

（1） i =0：nums[0]≠nums[1]，跳过这步操作。

（2） i =1：nums[1]=nums[2]，将nums[1]的值变成原来的2倍，nums[2]的值变成0，数组变成[1，4，0，1，1，0]。

（3） i =2：nums[2]≠nums[3]，跳过这步操作。

（4） i =3：nums[3]=nums[4]，将nums[3]的值变成原来的2倍，nums[4]的值变成0，数组变成[1，4，0，2，0，0]。

（5） i =4：nums[4]=nums[5]，将nums[4]的值变成原来的2倍，nums[5]的值变成0，数组变成[1，4，0，2，0，0]。

在执行完所有操作后，将0全部移动到数组的末尾，得到结果数组为[1，4，2，0，0，0]。

【限制】 2≤nums.length≤2000，0≤nums[ i ]≤1000。

【解法1】 整体建表法 。先用 i 遍历一次nums数组，当 i ＜ n -1且nums[ i ]=nums[ i +1]时做修改操作，即置nums[ i +1]=0，nums[ i ]=2nums[ i ]，然后采用1.2.2节中的思路将所有非0元素移动到最前面。实际上，这两步可以合并为一次遍历。本解法采用1.2.2节中解法1的思路将所有非0元素移动到最前面，最后将后面的元素用0填充。

【解法2】 元素移动法 。与解法1一样，用 i 遍历一次nums数组，当 i ＜ n -1且nums[ i ]=nums[ i +1]时做修改操作，即置nums[ i +1]=0，nums[ i ]=2nums[ i ]。本解法采用1.2.2节中解法2的思路将所有非0元素移动到最前面，最后将后面的元素用0填充。

【解法3】 区间划分法 。与解法1一样，用 i 遍历一次nums数组，当 i ＜ n -1且nums[ i ]=nums[ i +1]时做修改操作，即置nums[ i +1]=0，nums[ i ]=2nums[ i ]。本解法采用1.2.2节中解法3的思路将所有非0元素移动到最前面，最后将后面的元素用0填充。

1.2.4 LeetCode75——颜色的分类★★

【问题描述】 给定一个包含红色、白色和蓝色共 n 个元素的数组nums，对它们原地进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。这里使用整数0、1和2分别表示红色、白色和蓝色。另外，要求在不使用库内置的sort函数的情况下解决这个问题。

例如，nums=[2，0，2，1，1，0]，答案为[0，0，1，1，2，2]。

【限制】 n =nums.length，1≤ n ≤300，nums[ i ]为0、1或2。

【解法1】 区间划分法 。为了方便描述，将nums用 a 表示，用 i 从0开始遍历 a ，将 a [0.. n -1]划分为3个区间，如图1.9所示。其中， a [0.. j ]为0区间（初始为空，即 j =-1）， a [ j +1.. i -1]为1区间（初始为空，即 i =0）， a [ k .. n -1]为2区间（初始为空，即 k = n ）。

（1）若 a _i =0，将其移动到0区间的末尾，即执行 j ++，将 a _i 和 a _j 交换（新的 a _i 变为1，这样扩大0区间，1区间后移一个位置），再执行 i ++继续遍历 a 。

（2）若 a _i =2，将其移动到2区间的开头，即执行 k --，将 a _i 和 a _k 交换，这样扩大2区间，但新的 a _i 可能是1，也可能是0或者2，所以下一步需要继续处理 a _i ，因此不执行 i ++。

（3）若 a _i =1，不做任何操作，直接将 a _i 放置在1区间的末尾，再执行 i ++继续遍历 a 。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

【解法2】 计数排序法 。设置长度为3的数组 x ，其中 x [ i ]用于记录nums中值为 i （0≤ i ≤2）的元素的个数，遍历nums求出 x ，再将nums中的前 x [0]个元素置为0，中间 x [1]个元素置为1，最后的 x [2]个元素置为2。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.2.5 LeetCode189——轮转数组★★

【问题描述】 给定一个数组nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数，要求不返回任何值，在nums中就地轮转。

例如，nums=[1，2，3，4，5，6，7]， k =3，答案为[5，6，7，1，2，3，4]。

【限制】 1≤nums.length≤10 ⁵ ，-2 ³¹ ≤nums[ i ]≤2 ³¹ -1，0≤ k ≤10 ⁵ 。

【解题思路】 元素交换法 。对于给定的 k ， a 中后面 k 个元素为 a [ n - k .. n -1]，前面 n - k 个元素为 a [0.. n - k -1]，通过归纳发现以下规律：

（1） k ＞ n 时等同于向右轮转 k % n 个位置。

（2）当 k ＜ n 时以 k 为分割点将 a [0.. n -1]表示为 a [0.. n - k -1] a [ n - k .. n -1]，其轮转结果为 a [ n - k .. n -1] a [0.. n - k -1]，不妨将 a [0.. n - k -1]和 a [ n - k .. n -1]分别用 x 和 y 表示，用 x '表示 x 的逆置，而逆置是通过元素交换实现的。实际上，题目就是给定 xy ，求 yx ，显然有（ x ' y '）'=（ y '）'（ x '）'= yx ，因此将 x 和 y 分别逆置后再整个逆置就得到了轮转结果。

例如，对于题目中的样例， n =7， x =nums[0..3]=[1，2，3，4]， y =nums[4..6]=[5，6，7]， x '=[4，3，2，1]， y '=[7，6，5]， x ' y '=[4，3，2，1，7，6，5]，答案为（ x ' y '）'=[5，6，7，1，2，3，4]，如图1.10所示。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

或者

Python：

提交运行： VvPcfGszu7TrVop5ek5IXKRemcacSygOXqov8HJQI2b777DXEkBo1QIpHVHFD5fF