1.3 有序数组的算法设计

1.3.1 LeetCode26——删除有序数组中的重复项★

【问题描述】 给定一个升序排列的数组nums，请原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度，元素的相对顺序应该保持一致。由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么nums的前 k 个元素应该保存最终结果。注意，不要使用额外的空间，即算法的空间复杂度应该为 O （1）。

例如，nums=[0，0，1，1，1，2，2，3，3，4]，答案是返回5，nums=[0，1，2，3，4]，即函数返回新的长度5，并且原数组nums的前5个元素被修改为0、1、2、3、4，不需要考虑数组中超出新长度后面的元素。

【限制】 1≤nums.length≤3×10 ⁴ ，-10 ⁴ ≤nums[ i ]≤10 ⁴ ，nums已按升序排列。

【解法1】 整体建表法 。由于nums是有序的，其中重复的元素一定是相邻的。用nums存放结果，首先保留nums[0]， i 从1到 n -1循环，若nums[ i ]≠nums[ i -1]，则保留nums[ i ]，否则删除nums[ i ]，所以采用1.2.1节中解法1的思路删除所有满足条件nums[ i ]=nums[ i -1]的元素。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

【解法2】 元素移动法 。采用1.2.1节中解法2的思路，这里是删除所有满足条件nums[ i ]=nums[ i -1]（1≤ i ≤ n -1）的元素。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

【解法3】 区间划分法 。采用1.2.1节中解法3的思路，需要做以下几点修改：

（1）一定要保留nums[0]，初始保留区间必须含该元素，所以初始化 j =0而不是-1。

（2）该方法中nums[ i ]前面的元素nums[ i -1]可能发生更新，所以不能认为满足条件nums[ i ]=nums[ i -1]就判断nums[ i ]为重复元素，而是使用结果数组的判重方式，如果nums[ i ]=保留区间末尾的元素，即nums[ i ]=nums[ j ]，则nums[ i ]才是重复元素。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.2 LeetCode80——删除有序数组中的重复项Ⅱ★★

【问题描述】 给定一个有序数组nums，请原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。如果在删除重复项之后有 k 个元素，那么nums的前 k 个元素应该保存最终结果。注意，不要使用额外的空间，即算法的空间复杂度应该为 O （1）。

例如，nums=[1，1，1，2，2，3]，答案是返回5，并且原数组的前5个元素被修改为1、1、2、2、3，不需要考虑数组中超出新长度后面的元素。

【限制】 1≤nums.length≤3×10 ⁴ ，-10 ⁴ ≤nums[ i ]≤10 ⁴ ，nums已按升序排列。

【解法1】 整体建表法 。采用1.2.1节中解法1的思路，由于nums[ i ]前面的元素nums[ i -1]和nums[ i -2]可能发生更新，所以不能认为满足条件nums[ i ]=nums[ i -1]且nums[ i ]=nums[ i -2]就判断nums[ i ]为重复元素，而是使用结果数组的判重方式，若当前保留区间为nums[0.. k -1]（ k 为保留的元素的个数），如果nums[ i ]满足条件nums[ k -2]=nums[ k -1]且nums[ i ]=nums[ k -1]，则说明nums[ i ]是重复元素，删除之。由于nums中开头的两个元素一定是保留元素，所以初始化 k =2， i 从2开始遍历nums。

【解法2】 元素移动法 。采用1.2.1节中解法2的思路删除所有重复元素，重复元素的判定参考解法1， k 记录当前删除的元素的个数，对于当前遍历的元素nums[ i ]，保留区间的元素个数= i - k （nums[ i ]前面有 i 个元素，删除了 k 个元素，遍历 i - k 个元素），保留区间末尾的两个元素为nums[ i - k -1]和nums[ i - k -2]，若nums[ i - k -2]=nums[ i - k -1]且nums[ i ]=nums[ i - k -1]，说明nums[ i ]是重复元素，删除之。由于nums中开头的两个元素一定是保留元素，所以 i 从2开始遍历nums。

【解法3】 区间划分法 。采用1.2.1节中解法3的思路，需要做以下几点修改：

（1）一定要保留nums[0]和nums[1]，初始保留区间nums[0.. j ]必须含该元素，所以初始化 j =1而不是-1。 i 从2开始遍历nums。

（2）对于当前遍历的元素nums[ i ]，如果保留区间nums[0.. j ]中末尾的两个元素相同，并且它们与nums[ i ]也相同，则说明nums[ i ]是重复元素，也就是说满足条件！（nums[ j -1]=nums[ j ]且nums[ i ]=nums[ j ]）的元素nums[ i ]才是保留的元素。

1.3.3 LeetCode1287——有序数组中出现次数超过元素总数25%的元素★

【问题描述】 给定一个非递减的有序整数数组，已知这个数组中恰好有一个整数，它出现的次数超过数组元素总数的25%，请找到并返回这个整数。

例如，arr=[1，2，2，6，6，6，6，7，10]，其中 n =9，整数6出现了4次，答案为6。

【限制】 1≤arr.length≤10 ⁴ ，0≤arr[ i ]≤10 ⁵ 。

【解题思路】 通过有序性提高效率 。由于arr递增排序，这样所有相同的元素相邻排列。用c表示当前出现次数为cnt的字符（初始时置c=arr[0]，cnt=1），用 i 从1开始遍历arr：

（1）若arr[ i ]=c，说明等于c的元素增加了一个，执行cnt++。若cnt/（25%）=4*cnt＞ n ，则说明找到了满足要求的元素c，返回c即可。

（2）否则说明前面的c不可能是满足要求的元素，则从当前元素开始继续查找，即执行c=arr[ i ]，cnt=1。

上述过程经过一次遍历就可以找到答案，所以算法的时间复杂度为 O （ n ）。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.4 LeetCode1200——最小绝对差★

【问题描述】 给定一个整数数组arr，其中每个元素都不相同，请找到所有具有最小绝对差的元素对，并且按升序的顺序返回。每个元素对[ a ， b ]如下： a 和 b 均为数组arr中的元素， a ＜ b 时 b - a 等于arr中任意两个元素的最小绝对差。

例如，arr=[4，2，1，3]，答案是[[1，2]，[2，3]，[3，4]]。

【限制】 2≤arr.length≤10 ⁵ ，-10 ⁶ ≤arr[ i ]≤10 ⁶ 。

【解题思路】 排序 + 通过有序性提高效率 。用ans存放结果，先将arr递增排序，置最小绝对差mind为arr[ n -1]-arr[0]。用 i 从1到 n -1遍历arr：

（1）若arr[ i ]-arr[ i -1]＜mind，说明找到一个新的最小绝对差，置ans为空，将该元素对{arr[ i -1]，arr[ i ]}添加到ans中。

（2）若arr[ i ]-arr[ i -1]=mind，说明找到具有最小绝对差的另外一个元素对，将该元素对{arr[ i -1]，arr[ i ]}添加到ans中。

（3）若为其他情况，说明{arr[ i -1]，arr[ i ]}不是具有最小绝对差的元素对，跳过。

最后返回ans即可。

例如，arr=[1，5，3，6，7]，排序后arr=[1，3，5，6，7]，置mind=7-1=6，ans=[]：

（1） i =1，arr[1]-arr[0]=2＜mind，置mind=2，ans=[]，向ans中添加[1，3]，ans=[[1，3]]。

（2） i =2，arr[2]-arr[1]=2=mind，向ans中添加[5，3]，ans=[[1，3]，[3，5]]。

（3） i =3，arr[3]-arr[2]=1＜mind，置mind=1，ans=[]，向ans中添加[6，5]，ans=[[6，5]]。

（4） i =4，arr[4]-arr[3]=1=mind，向ans中添加[7，6]，ans=[[6，5]，[7，6]]。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.5 LeetCode88——合并两个有序数组★

【问题描述】 给定两个按非递减顺序排列的整数数组nums1和nums2，另外有两个整数 m 和 n ，分别表示nums1和nums2中元素的数目，请合并nums2到nums1中，并使合并后的数组同样按非递减顺序排列。注意，最终合并后的数组不应该由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为 m + n ，其中前 m 个元素表示应该合并的元素，后 n 个元素为0，应该忽略；nums2的长度为 n 。

例如，nums1=[1，2，3，0，0，0]， m =3，nums2=[2，5，6]， n =3，答案是nums1=[1，2，2，3，5，6]。

【限制】 nums1.length= m + n ，nums2.length= n ，0≤ m ， n ≤200，1≤ m + n ≤200，-10 ⁹ ≤nums1[ i ]，nums2[ j ]≤10 ⁹ 。

进阶：设计一个时间复杂度为 O （ m + n ）的算法解决此问题。

【解题思路】 二路归并法 。为了描述简单，分别用 a 和 b 表示nums1和nums2数组。由于题目需要将全部归并的元素存放到 a 中，所以必须从后面开始放置元素，为此使用二路归并过程，用 i 和 j 分别从前向后遍历 a 和 b ，看成两个递减序列的二路归并，每次归并较大的元素并且存放在 a _k 处， k 表示归并元素的位置（从 m + n -1开始），如图1.11所示。

1.3.6 LeetCode349——两个数组的交集★

【问题描述】 给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的，可以不考虑输出结果的顺序。

例如，nums1=[1，2，2，1]，nums2=[2，2]，答案为[2]。

【限制】 1≤nums1.length，nums2.length≤1000，0≤nums1[ i ]，nums2[ i ]≤1000。

【解题思路】 排序 + 二路归并法 。先将两个数组递增排序，再使用二路归并求交集。这里要求结果中的每个元素是唯一的，为此在生成结果数组ans时考虑除重，即仅将不等于ans末尾元素的当前归并元素添加到ans中，最后返回ans即可。

1.3.7 LeetCode977——有序数组的平方★

【问题描述】 给定一个按非递减顺序排序的整数数组nums，返回由每个数字的平方组成的新数组，要求也按非递减顺序排序。

例如，nums=[-4，-1，0，3，10]，所有元素平方后数组变为[16，1，0，9，100]，排序后数组变为[0，1，9，16，100]。

【限制】 1≤nums.length≤10 ⁴ ，-10 ⁴ ≤nums[ i ]≤10 ⁴ ，nums已按非递减顺序排序。

进阶：设计一个时间复杂度为 O （ n ）的算法解决本问题。

【解题思路】 二路归并法 。用ans存放答案，首先对nums中的所有元素做平方运算，找到其中的最小元素nums[mini]=mind，然后将mind添加到ans中，显然mind元素对应的原整数（mind做平方运算之前的整数）一定是绝对值最小者，根据平方运算的特点和有序性可知，从nums[mini]向左、右两边扩展一定是递增的，即nums[0..mini-1]是递减的（反向遍历时看成递增序列），nums[mini+1.. n -1]是递增的，可以将两个有序序列使用二路归并得到递增序列ans，最后返回ans。

例如，nums=[-4，-1，0，3，10]，求解过程如图1.12所示。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.8 LeetCode1470——重新排列数组★

【问题描述】 给定一个数组nums，数组中有2 n 个元素，按[ x ₁ ， x ₂ ，…， x _n ， y ₁ ， y ₂ ，…， y _n ]格式排列，请将数组按[ x ₁ ， y ₁ ， x ₂ ， y ₂ ，…， x _n ， y _n ]格式重新排列，返回重新排列后的数组。

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

【限制】 1≤ n ≤500，nums.length=2 n ，1≤nums[ i ]≤1000。

【解题思路】 二路归并 + 整体建表法 。将奇数序号的元素看成一个序列，将偶数序号的元素看成另一个序列，这里两个序列中元素的个数均为 n ，使用与二路归并类似的过程交替归并两个序列中的元素产生ans，最后返回ans。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.9 LeetCode1213——3个有序数组的交集★

【问题描述】 给定3个均为严格递增排列的整数数组arr1、arr2和arr3，返回一个由仅在这3个数组中同时出现的整数所构成的有序数组。

例如，arr1=[1，2，3，4，5]，arr2=[1，2，5，7，9]，arr3=[1，3，4，5，8]，答案为[1，5]。

【限制】 1≤arr1.length，arr2.length，arr3.length≤1000，1≤arr1[ i ]，arr2[ i ]，arr3[ i ]≤2000。

【解题思路】 三路归并法 。用ans数组存放最后的结果（初始为空），用 i 、 j 和 k （遍历指针）分别遍历3个数组arr1、arr2和arr3，约定这3个数组的段号依次为0～2，设置长度为3的数组 x ， x [ i ]（0≤ i ≤2）存放第 i 段的当前元素。

先置 x ={arr1[0]，arr2[0]，arr3[0]}，设置3个段的遍历指针 i = j = k =0。在3个段都没有遍历完时循环：

（1）若 x 中的3个元素均相同，则将该元素插入ans的末尾（除重），执行 i ++， j ++， k ++，在指针有效时将所指元素置入 x 中相应的位置。

（2）否则求出 x 中最小元素的段号mini，将对应的指针后移一个位置，在指针有效时将所指元素置入 x 中相应的位置。

最后返回ans。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

另外，可以将3个数组转换为集合，使用集合求交集运算求出3个集合的交集，最后将结果排序后返回。对应的算法如下：

Python：

提交运行：

1.3.10 LeetCode264——丑数Ⅱ★★

【问题描述】 给定一个整数 n ，请找出并返回第 n 个丑数。丑数就是只包含质因数2、3或5的正整数。

例如， n =10，[1，2，3，4，5，6，8，9，10，12]是由前10个丑数组成的序列，答案为12。

【限制】 1≤ n ≤1690。

【解题思路】 三路归并法 。根据丑数的定义，若 m 是一个丑数，则2 m 、3 m 和5 m 一定是丑数。对于给定的 n ，用ans[1.. n ]存放前 n 个丑数（下标0不用）。

首先置ans[1]=1，即1是第一个丑数，则2倍的丑数序列=[2，4，6，8，…]，3倍的丑数序列=[3，6，9，12，…]，5倍的丑数序列=[5，10，15，20，…]。然后使用三路归并求前 n 个丑数即可，如图1.13所示为求前10个丑数的过程。

用p2、p3和p5遍历2、3和5倍的丑数序列（均从1开始），求出归并的最小值mind，并将相应的指针后移。实际上没有必要单独存放2、3和5倍的丑数序列，ans包含全部丑数，所以只需要ans即可。除了初始置ans[1]=1外再归并 n -1次，最后返回ans[ n ]。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

1.3.11 LeetCode373——查找和最小的 k 对数字★★

【问题描述】 给定两个升序排列的整数数组nums1和nums2，以及一个整数 k ，定义一对值（ u ， v ），其中第一个元素来自nums1，第二个元素来自nums2，请找到和最小的 k 个数对（ u ₁ ， v ₁ ）、（ u ₂ ， v ₂ ）、……、（ u _k ， v _k ）。

例如，nums1=[1，7，11]，nums2=[2，4，6]， k =3，全部数对为[1，2]、[1，4]、[1，6]、[7，2]、[7，4]、[11，2]、[7，6]、[11，4]、[11，6]，和最小的前3个数对是[1，2]、[1，4]、[1，6]。

【限制】 1≤nums1.length，nums2.length≤10 ⁵ ，-10 ⁹ ≤nums1[ i ]，nums2[ i ]≤10 ⁹ ，nums1和nums2均为升序排列，1≤ k ≤1000。

【解题思路】 多路归并 + 整体建表法 。为了描述简单，将两个数组nums1和nums2分别用 a 和 b 表示。假设 a 和 b 中元素的个数分别为 m 和 n ，图1.14列出了全部的 a _i + b _j （0≤ i ≤ m -1，0≤ j ≤ n -1），由于 a 和 b 是递增的，则每一行也是递增的，将每一行看成一个递增有序序列，这样共有 m 个有序序列，使用 m 路归并（参见1.1.2节的多路归并法）求前面和最小的 k 个数对ans，最后返回ans即可。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

说明： 考虑最坏情况，当 k 取最大值 mn 时，参与归并的元素的个数为 mn ，mink（）算法在 m 个元素中通过简单比较找和最小的元素，算法的复杂度为 O （ m ），所以整个算法的时间复杂度为 O （ m ² n ），因此出现超时。 WRJdJx0JH9/PcdqCaG5DkVou7iN8R7CeljAB+4PGzo3RDoHSfgBKKXVm2uQCF66S