使用函数指针完成数组的排序_使用函数指针完成数组的排序操作

面试高频算法题之数组 　　大家好，我是程序员学长~ 　　今天给大家带来一篇面试高频算法题之数组的详细解析，全文包含19道大厂笔试面试算法真题，一举拿下数组这个知识点，让算法不在成为进入大厂的绊脚石。 　　如果喜欢，记得点个哟~ 　　本文有点长，我已将本文制作成带目录的PDF版本，本文PDF版本，请私信我。 　　1全文概览 　　

　　2数组的基础知识 　　数组的定义及特点 　　数组是一种线性表数据结构，是在连续内存空间上的存储相同类型数据的集合。

　　数组主要有以下特点。数组的下标是从0开始的。连续的内存空间和相同的数据类型。 　　正是因为数组的内存空间是连续的，所以我们可以“随机访问”数组内的素。但有利有弊，如果想要在数组中插入或者删除一个素，为了保证数组的内存空间的连续，就难免要移动其他素。 　　例如要删除下标为2的素，需要对下标2后面的素都需要向前移动。如图所示：

　　解题有妙招 　　二分法 　　如果给定的数组是有序的，我们就需要考虑是否可以使用二分法来求解（二分法的时间复杂度是O(logn)）。面试中二分法是面试中常考的知识点，建议大家一定要多锻炼手撕二分的能力。 　　双指针法 　　我们可以通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。例如，当我们需要枚举数组中的两个素时，如果我们发现随着第一个素的递增，第二个素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2)减低到O(N)。 　　滑动窗口 　　顾名思义，所谓的滑动窗口就是可以在一个序列上进行滑动的窗口。其中窗口大小有固定长度的，也有可变长度的。例如给定数组[2,2,3,4,8,99,3]，窗口大小为3，求出每个窗口的素和就是固定大小窗口的问题，如果求数组[2,2,3,4,8,99,3]的最长连续子数组就是窗口可变的问题。使用滑动窗口，我们可以减低算法是时间复杂度。 　　使用滑动窗口求解问题时，主要需要了解什么条件下移动窗口的起始位置，以及何时动态的扩展窗口，从而解决问题。 　　哈希表法 　　如果需要在数组中查找某个素是否存在时，我们可以使用哈希表法，可以将查找素的时间复杂度从O(n)减低到O(1)。 　　3两数之和 　　问题描述 　　LeetCode 1. 两数之和 　　给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个素在答案里不能重复出现。你可以按任意顺序返回答案。 　　示例 1： 　　输入：nums = [2,7,11,15], target = 9 　　输出：[0,1] 　　解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 　　分析问题 　　拿到这个问题，最简单直观的想法就是对于数组中的每个素x，去寻找数组中是否存在target-x。 　　我们可以很清楚的知道，这个算法的时间复杂度是O(n^2)。那我们该如何降低时间复杂度呢？可以注意到该算法复杂度高的原因在于寻找素target-x的时候，需要遍历一遍数组，所以我们需要对这一块进行优化。我们可以采用哈希表，将寻找素target-x的时间复杂度由O(n)降低到O(1)。 　　我们在遍历数组时，对于每个素x，我们首先查询哈希表中是否存在target-x，如果存在，将匹配到的结果直接返回，如果不存在，我们把x插入到哈希表中。

　　Tips: 我们这里使用字典来代替哈希表，当插入的素重复时，我们覆盖就好了，这样可以保证查找的时间复杂度为O(1)。为什么这里可以覆盖呢，因为题目要求是找两个数和等于target，当有两个素重复时，我们认为它们是等价的，所以我们只需要保留一个就好了。 　　我们可以看到该算法的时间复杂度是O(n)，空间复杂度也是O(n)。 　　优化 　　当我们需要枚举数组中的两个素时，如果我们发现随着第一个素的递增，第二个素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2)减低到O(N)。 所以我们可以采用双指针法来求解。首先，我们先对数组进行排序，然后用left和right指针分别指向数组的左边和右边，此时sum=nums[left]+nums[right]，根据sum和target的大小关系，我们来移动指针。如果sum>target，右指针左移，减小sum的值，即right=right-1。如果sum<target，左指针右移，增大sum的值，即left=left+1。如果sum=target，直接返回。

　　下面我们来看一下代码的实现。 　　利用sorted进行排序，时间复杂度是O(nlogn)，空间复杂度是O(n)。所以该算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。 　　4最长无重复子数组 　　问题描述 　　LeetCode3. 无重复字符的最长子串 　　给定一个数组arr，返回arr的最长无重复素子数组的长度，无重复指的是所有数字都不相同。子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。 　　示例 　　输入：[2,2,3,4,8,99,3] 　　返回值：5 　　说明：[2,3,4,8,99]是最长子数组 　　分析问题 　　在开始之前，我们首先介绍一下什么是滑动窗口。顾名思义，所谓的滑动窗口就是可以在一个序列上进行滑动的窗口。如图所示，假设，我们的序列为abcabcbb，我们这里定义了一个固定大小为3的窗口在序列上滑来滑去。

　　在实际的使用中，我们使用的滑动窗口都是可变长度的。 　　我们可以使用双指针来维护窗口的开始和结束，通过移动左、右指针来实现窗口大小的改变和窗口的滑动。 　　我们来看一下题目，题目是求最长无重复素子数组，如果我们可以求出所有的无重复素的子数组，那取出最长的不就好了。下面我们来看一下如何求解。我们只需要维护一个在数组中进行滑动的窗口就好。开始时2不在窗口中，所以扩大窗口。

下一个素2在窗口中出现，所以我们要将出现过的素及其左边的素统统移出窗口，即2。

接下来的素3、4、8、99都没在窗口中出现过，所以我们把它们都加入到窗口中。

下一个素3在窗口出现过，所以我们要移除出现过的素及其左边的素，即2，3。

　　下面我们来看一下代码如何实现。 　　该算法的时间复杂度是O(n)。 　　5合并两个有序数组 　　问题描述 　　LeetCode 88. 合并两个有序数组 　　给你两个按非递减顺序排列的整数数组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 　　输出：[1,2,2,3,5,6] 　　解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] 。 　　分析问题 　　最简单暴力的方法就是直接把nums2放入nums1的后n个位置，然后直接对nums1进行排序就好了。我们这里就不在赘述。 　　那么既然给定的两个数组是有序的，那我们何不把这个条件利用起来，来优化代码。所以，我们可以使用两个指针p1和p2分别指向两个数组的起始位置，然后比较大小，将较小的放入结果中，然后指针后移，直到将所有素都排好序。





　　下面我们来看一下代码的实现。 　　我们可以知道这里的时间复杂度是O(m+n)，空间复杂度也是O(m+n)。 　　优化 　　在使用双指针法时，我们从前往后遍历数组，如果直接使用nums1存储合并结果的话，nums1 中的素可能会在取出之前被覆盖。所以我们引入了一个临时变量sorted来存储。那有什么办法可以避免nums1中的素被覆盖呢？既然从前往后不可以，那么我们能从后往前吗？因为nums1的后半部分是空的，可以直接覆盖而不会影响结果，所以这里引入了逆向双指针法。



　　我们来看一下代码实现。 　　该算法的时间复杂度是O(m+n)，空间复杂度是O(1)。 　　6螺旋矩阵 　　问题描述 　　LeetCode 54. 螺旋矩阵 　　给你一个 行 列的矩阵 ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有素。 　　示例： 　　输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 　　输出：[1,2,3,6,9,8,7,4,5]

　　分析问题 　　题目要求是按照顺时针螺旋顺序输出，即先从左到右、然后从上到下、再从右到左、最后从下到上，依次类推，直到全部素遍历完为止。在遍历的过程中，最关键的一点就是要记录哪些素已经被访问过了，如果遇到被访问过的素，我们就需要顺时针的调整一下方向。 　　判断素是否被访问过，最直观的想法就是声明一个和矩阵大小相同的矩阵，来标识矩阵中的素是否被访问过。 　　我们来看一下代码如何实现。 　　由于创建了一个和原始矩阵一样大小的矩阵来表示素是否被访问过，所以该算法的空间复杂度是O(mn)。矩阵中的素都会被遍历一次，所以该算法的时间复杂度也是O(mn)。 　　优化 　　那有什么方法可以优化算法的空间复杂度吗？即我们不用开辟新的空间来保存矩阵中的素是否被访问过。 　　其实我们可以在遍历的过程中不断的改变边界条件，当矩阵的第一行素被访问过之后，那上边界就需要进行+1操作；如果最后一列素被访问过了，那么右边界需要进行-1操作；如果最后一行素被访问过了，那下边界需要进行-1操作；如果第一列被访问过了，那需要进行+1操作；依次类推，直到遍历完成。

　　该算法的时间复杂度是O(m*n)，空间复杂度是O(1)。 　　7数组中和为 0 的三个数 　　问题描述 　　LeetCode 剑指 Offer II 007. 数组中和为 0 的三个数 　　给定一个包含n个整数的数组nums，判断nums中是否存在三个素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且不重复的三组。 　　示例： 　　输入：nums = [-1,0,1,2,-1,-4] 　　输出：[[-1,-1,2],[-1,0,1]] 　　分析问题 　　这道题目算是二数之和的升级版，所以我们也可以采用双指针法来求解。那三个数如何采用双指针法呢，其实很简单，我们先把一个数固定下来，然后另外两个数再使用双指针去寻找不就好了。按照惯例，我们首先对数组进行排序，然后固定第一个数first，假设为nums[i]，然后再使用双指针法在数组中寻找两数之和等于-nums[i]即可。由于题目要求所求的三组是不重复的，所以需要判断去掉重复解。重复解主要有以下两种情况。当nums[first]=nums[first-1]，由于我们已经把第一个素是nums[first-1]的三组已经求解过了，所以没必要重复求解。当nums[first]+nums[left]+nums[right]=0时，如果nums[left]=nums[left+1]或者nums[right]=nums[right+1]，会导致重复解，所以需要去掉。

　　我们来看一下代码的实现。 　　8数组中出现次数超过一半的数字 　　问题描述 　　LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字 　　给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 　　示例： 　　输入：[1,2,3,2,2,2,5,4,2] 　　输出：2 　　分析问题 　　哈希表法 　　我们最容易想到的方法就是使用哈希表法，去统计每个数字出现的次数，即可很容易的求出众数。 　　该算法的时间复杂度是O(n)，空间复杂度也是O(n)。 　　排序算法 　　我们将数组进行排序，那排序后的数组的中点一定就是众数。 　　Boyer-Moore 投票算法 　　这道题最经典的解法是Boyer-Moore 投票算法。Boyer-Moore 投票算法的核心思想是票数正负抵消，即遇到众数时，我们把票数+1，遇到非众数时，我们把票数-1，则所有的票数和一定是大于0的。 　　我们假设数组nums的众数是x，数组的长度为n。我们可以很容易的知道，若数组的前a个数字的票数和为0，那么剩余n-a个数字的票数和一定是大于0的，即后n-a个数字的众数仍然为x。

　　我们记数组的首个素是n1，数组的众数是x，遍历并统计票数。当发生票数和为0时，数组剩余素的众数一定也是x，这是因为：当n1等于x时，抵消的所有数字中，有一半是众数x。当n1不等于x时，抵消的所有数字中，众数的个人最少为0，最多为一半。 　　所以，我们在去掉m个字符里，最多只去掉了一半的众数，所以在剩余的n-m个素中，x仍然为众数。利用这个特性，在每次遇到票数和为0时，我们都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　9合并区间 　　问题描述 　　LeetCode 56. 合并区间 　　以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 　　输入：intervals = [ [1，3]，[2，6]，[8，10]，[15，18] ] 输出：[ [1，6]，[8，10]，[15，18] ] 解释：区间 [1，3] 和 [2，6] 重叠，将它们合并为 [1，6] 　　分析问题 　　对于任意两个区间A和B，它们之间的关系可以有以下6种情况。

　　我们将这两个区间进行比较、交换，使得第一个区间的起始位置 ≤ 第二个区间的起始位置这个条件成立，这样的话，我们就可以把这6种情况转换成以下3种。

　　按照这个思路，我们将所有区间按照左端点进行排序，那么就可以保证任意连续的两个区间，第一个区间的起始位置 ≤ 第二个区间的起始位置，所以他们的关系只有上面三种情况。 　　算法 　　对于上面的三种情况，我们可以采用如下算法来求解。 　　首先，我们用数组 merged 存储最终的答案。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，即上图中的第二种情况，那么它们不会重合。我们可以直接将这个区间加入数组 merged 的末尾； 否则，它们是有重合部分的，即上图中的第一、三种情况，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。 　　这样，我们就可以解决上述的三种情况，下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(nlogn)，其中n是区间的数量，除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O*(*n logn)。空间复杂度是O(logn)。 　　10在两个长度相等的排序数组中找到上中位数 　　问题描述 　　LeetCode 4. 寻找两个正序数组的中位数 　　给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。上中位数：假设递增序列长度为n，为第n/2个数。 　　要求：时间复杂度 O (n)，空间复杂度 O(1)。 　　进阶：时间复杂度为O(logN)，空间复杂度为O(1)。 　　示例： 　　输入：[1，2，3，4]，[3，4，5，6] 　　返回值：3 　　说明：总共有8个数，上中位数是第4小的数，所以返回3。 　　分析问题 　　这道题最直观的想法就是，使用归并排序的方式，将两个有序数组合并成一个大的有序数组。大的有序数组的上中位数为第n/2个数。我们可以知道该算法的时间复杂度是O(N)，空间复杂度也是O(N)，显然不符合题目要求的O(1)的空间复杂度。其实，我们也不需要合并两个有序数组，我们只需要找到上中位数的位置即可。对于给定两个长度为N的数组，我们可以知道其中位数的位置为N，所以我们维护两个指针，初始时分别指向两个数组的下标0的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组的末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。



　　下面我们来看一下代码如何实现。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　进阶 　　下面我们来看一下如何把时间复杂度降低为O(logN)。我们这里可以采用二分查找的思想来求解。 　　对于长度为N的数组arr1和arr2来说，它的上中位数是两个有序数组的第N个素。所以，我们把这道题目可以转换成寻找两个有序数组的第k小的素，其中k=N。 　　要找到第N个素，我们可以比较arr1[N/2-1]和arr2[N/2-1]，其中“/”代表整数除法。由于arr1[N/2-1]和arr2[N/2-1]的前面分别有arr1[0…N/2-2]和arr2[0…N/2-2]，即N/2-1个素。对于arr1[N/2-1]和arr2[N/2-1]的较小值，最多只会有N/2-1+N/2-1=N-2个素比它小，所以它不是第N小的素。 　　因此，我们可以归纳出以下三种情况。如果arr1[N/2-1] < arr2[N/2-1]，则比arr1[N/2-1] 小的数最多只有 arr1的前N/2-1个数和arr2的前N/2-1个数，即比arr1[N/2-1] 小的数最多只有N-2个，因此arr1[N/2-1]不可能是第N个数，arr1[0]到arr1[N/2-1]也都不可能是第N个数，所以可以删除。如果arr1[N/2-1] > arr2[N/2-1]，则可以排除arr2[0]到arr2[N/2-1]。如果arr1[N/2-1]==arr2[N/2-1]，可以归为第一种情况进行处理。 　　可以看到，经过一轮比较后，我们可以排查N/2个不可能是第N小的数，查找范围缩小了一半。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 N 的值，这是因为我们排除的数都不大于第 N 小的数。 　　下面我们来看一个具体的例子。



　　加餐 　　如果给定的两个有序数组大小不同，即给定两个大小分别为 和 的正序（从小到大）数组 和 。请你找出并返回这两个正序数组的 中位数 。 　　根据中位数的定义，当m+n为奇数时，中位数是两个有序数组的第(m+n+1)/2个素。当m+n为偶数时，中位数是两个有序数组的第(m+n)/2和(m+n)/2+1个素的平均值。因此这道题我们可以转化成寻求两个有序数组的第k小的数，其中k为(m+n)/2或者(m+n)/2+1。 　　所以该题的解题思路和上一题的解法类似，不过这里有一些情况需要特殊处理。如果nums1[k/2-1]或者nums[k/2-1]越界，那么我们需要选择对应数组的最后一个素，即min(k/2-1,m-1)或者min(k/2-1,n-1)。如果一个数组为空，我们可以直接返回另一个数组中第 k 小的素。如果k=1，我们只需要返回两个数组首素的最小值即可。 　　下面我们来看一下代码的实现。





　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(log(m+n))，空间复杂度是O(1)。 　　11缺失的第一个正整数 　　问题描述 　　LeetCode 41. 缺失的第一个正数 　　给你一个无重复素未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 　　请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。 　　示例： 　　输入：nums = [1，2，0] 　　输出：3 　　分析问题 　　对于一个无重复素、长度为N的数组，其中没有出现的最小整数只能在[1,N+1]中，这是因为如果[1,N]在数组中都出现了，说明这N个数已经把数组填满了，那么答案是N+1，否则就是[1，N]中没有出现的最小整数。所以，我们可以申请一个辅助数组temp，大小为N，我们通过遍历原数组，将属于[1,N]范围内的数，放入辅助数组中相应的位置，使得temp[i-1] = i 成立。在遍历完成后，temp中第一个不满足temp[i-1] = i 条件的就是最小的正整数，如果都满足，那么最小正整数就是N+1。





　　下面我们来看一下代码实现。 　　我们可以知道该算法的时间复杂度和空间复杂度都是O(n)，显然空间复杂度不满足题目要求，那我们该如何降低算法的空间复杂度呢？通过观察，我们可以发现辅助数组和原数组大小一样，那么我们能否复用原数组nums呢？答案显然是可以的。我们在遍历数组的过程中，假设遍历到的素值为x，如果x属于[1,N]，我们将素x和nums[x-1]的素进行互换，使得x出现在正确的位置上，否则不做处理。当遍历完成后，nums中第一个不满足nums[i-1] = i 条件的就是最小的正整数，如果都满足，那么最小正整数就是N+1。



　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　12顺时针旋转数组 　　问题描述 　　LeetCode 面试题 01.07. 旋转矩阵 　　有一个 NxN 整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。 　　要求：时间复杂度O(N^2)，空间复杂度是O(N^2)。 　　进阶：时间复杂度是O(N^2)，空间复杂度是O(1) 　　示例： 　　分析问题 　　对于矩阵中的第一行素来说，在经过90度旋转后，出现在了倒数第一列的位置上，如下图所示。

　　并且，第一行的第 i 个素在旋转后恰好是倒数第一列的第 i 个素。对于第二行的素也是如此，在旋转后变成倒数第二列的素，并且第二行的第i个素在旋转后恰好是倒数第二列的第i个素。所以，我们可以得出规律，对于矩阵中第 i 行的第 j 个素，在旋转后，它出现在倒数第 i 列的第 j 个位置，即对于矩阵中的 matrix[i] [j] 素，在旋转后，它的新位置为 matrix [j] [n-i-1]。 　　所以，我们申请一个大小为 n * n 的新矩阵，来临时存储旋转后的结果。我们通过遍历matrix中的所有素，根据上述规则将素存放到新矩阵中的对应位置。在遍历完成后，再将新矩阵中复制到原矩阵即可。下面我们来看一下代码实现。 　　该算法的时间复杂度是O(N^2)，空间复杂度O(N^2)。 　　进阶 　　那我们如何在不使用辅助空间的情况下，实现矩阵的原地旋转呢？我们来看一下方法一中为什么要引入辅助空间，对于matrix中的素，我们使用公式temp[j] [n – i – 1] = matrix[i] [j]进行旋转，如果不申请辅助矩阵，我们直接把素 matrix[i] [j]，放到矩阵 matrix[j] [n – i – 1]位置，原矩阵中的matrix[j] [n – i – 1]素就被覆盖了，这显然不是我们要的结果。





　　当知道了如何原地旋转矩阵之后，这里还有一点需要明确：我们应该选取哪些位置进行上述的原地交换操作呢？通过上面的分析可以知道，一次可以原地交换四个位置，所以：当n为偶数时，我们需要选取 n^2 / 4 = (n/2) * (n/2)个素进行原地交换操作，可以将该图形分为四块，可以保证不重复、不遗漏旋转所有素；当n为奇数时，由于中心的位置经过旋转后位置不变，我们需要选取 (n^2-1)/4=(n-1)/2 * (n+1) /2个素进行原地交换操作，我们以5*5的矩阵为例，可以按照以下方式划分，进而保证不重复、不遗漏的旋转所有素。

　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。 　　##数组中的最长连续子序列 　　问题描述 　　LeetCode128. 最长连续序列 　　给定无序数组arr，返回其中最长的连续子序列的长度(要求值连续，位置可以不连续，例如 3,4,5,6为连续的自然数）。请你设计并实现时间复杂度为 的算法解决此问题。 　　示例： 　　输入：[100,4,200,1,3,2] 　　输出：4 　　说明：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 　　分析问题 　　因为给定的数组是无序的，所以我们最直观的想法就是遍历数组中的每个素，然后考虑以其为起点，不断的在数组中寻找x+1，x+2，…，x+n是否存在，如果最长匹配到了x+n，那么就表明以x为起点的最长连续序列为x，x+1，x+2，…，x+n，其长度为n+1。因为在数组中寻找一个数是否存在，是需要O(n)的时间复杂度；而在哈希表中判断一个数是否存在只需要O(1)的时间复杂度，所以我们可以通过引入一个哈希表，来减低该算法的时间复杂度。 　　在最坏的情况下，该算法的时间复杂度是O(n^2)（即外层需要枚举n个数，内层也需要匹配n次），无法满足题目的要求，那我们如何来进行优化呢？ 　　我们来分析一下算法的执行过程，如果我们已经知道了数组中存在有一个x，x+1，x+2，…，x+n的连续序列，那么我们就没有必要再继续以x+1，x+2，….，x+n为起点去数组中寻找连续序列了，因为得到的结果肯定不会优于以x为起点的连续序列。所以，我们在外层循环中如果碰到这种情况直接跳过就好。 　　具体做法是，我们在遍历的素x时，去判读其前驱数x-1是否存在，如果存在的话，就不需要执行后面的逻辑，因为从x-1进行匹配的结果是优于从x进行匹配的，所以跳过x。





　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(n)，空间复杂度也是O(n)。 　　13寻找峰值 　　问题描述 　　LeetCode 162. 寻找峰值 　　峰值素是指其值严格大于左右相邻值的素。给你一个整数数组 nums，找到峰值素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 　　示例： 　　输入：nums = [1,2,3,1] 　　输出：3 是峰值素，你的函数应该返回其索引 2。 　　分析问题 　　峰值是指其值严格大于左右相邻值的素，那么很显然数组中的最大值一定是一个峰值，因为它肯定大于它左右两侧的素。所以，我们可以对数组进行一次遍历，然后求出其最大值的位置即可。该算法的时间复杂度是O(n)，是不满足题目要求的。那我们如何进行优化呢。 　　我们可以这么来考虑，如果我们从一个位置开始，不断地向高处走，那么最终一定可以到达一个峰值位置。 　　因此，我们首先在 [0, n) 的范围内随机一个初始位置 i，随后根据nums[i-1]，nums[i]，nums[i+1]三者的关系决定向哪个方向走。如何nums[i-1] < nums[i] > nums[i+1]，那么位置i就是峰值的位置，我们直接返回i。如果nums[i-1] < nums [i] < nums[i+1] , 那么位置i处于上坡位置，要想找到峰值，需要往右走，即i=i+1。如果nums[i-1] > nums[i] > nums[i+1]，那么位置i处于下坡位置，要想找到峰值，需要往左走，季i=i-1。如果nums[i-1] > nums[i] < nums[i+1]，此时i处于坡底，要想找到峰值，两个方向都可以，我们假设这种情况需要往右边走。 　　综上所述，当i不是峰值时。如果nums[i] > nums[i+1] , i需要往左走，即执行i=i-1。如果nums[i] < nums[i+1]，i需要往右走，即执行i=i+1。 　　在最坏的情况下，假设nums是单调递增的，并且我们是从0开始出发的，那这样就需要一直向右走到数组的最后一个位置，该算法的时间复杂度是O(n)，而题目要求的时间复杂度是O(logn)，显然是不符合的，那我们该如何求解呢？对于像O(logn)这种形式的时间复杂度，我们最先想到的就是二分法，但是数组中的素又不是排序的，那我们该如何使用二分法来求解此题呢？下面我们就来看一下。 　　通过分析，我们可以发现，当nums[i] < nums[i+1]时，我们需要让i向右走，即执行i=i+1，那么i和i左边的所有位置在后续的迭代中是永远不会走到的。因为假设此时在i+1的位置，要想向左走到位置i，就需要nums[i] > nums[i+1]，显然是不可能的。所以我们可以设计如下算法，首先创建两个变量l、r表示可走的左、右边界，开始时l=0，r=n-1。取区间[l，r]的中点，即mid=(l+r)/2。如果下标mid是峰值，直接返回。如果nums[mid] < nums[mid+1]，表示峰值在mid的右边，所以抛弃区间[l，mid]，在剩余的[mid+1，r]的区间内去寻找。如果nums[mid] > nums[mid+1]，表示峰值在mid的左边，所以抛弃区间[mid, r]，在剩余的[l，mid-1]的区间内去寻找。 　　这样的话，该算法每次淘汰掉一半的素，所以时间复杂度是O(logn)。



　　下面我们来看一下代码的实现。 　　14二维数组中的查找 　　问题描述 　　LeetCode 剑指 Offer 04. 二维数组中的查找 　　在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 　　示例： 　　现有矩阵 matrix 如下： 　　给定 target = ，返回 。 　　给定 target = ，返回 。 　　分析问题 　　在二维数组中去查找一个素，我们可以遍历一遍二维数组中的每一个素，然后去判断是否和目标值相同。该算法的时间复杂度是O(m*n)，它显然不是最优的解法。我们接下来来看一下如何进行优化。 　　因为给定的数组中的每一行、每一列都是递增排列的。当我们以左下角为起点时，只有向上和向右两种选择，上边的值严格的小，右边的值严格的大。所以，我们可以利用这个性质。 　　我们从二维数组的左下角为起点，开始遍历数组。当素matrix [i] [j] < target，说明target在matrix [i] [j]的右方，所以向右走，即执行 j=j+1。当素matrix [i] [j] > target，说明target在matrix [i] [j]的上方，所以向上走，即执行 i= i-1。当素matrix [i] [j] == target，代表已经找到了目标值，直接返回true即可。 　　最后，当超出二维数组的边界时，表示数组中不存在该素，直接返回false。





　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(m+n)，空间复杂度是O(1)。 　　15数组中的逆序对 　　问题描述 　　LeetCode 剑指 Offer 51. 数组中的逆序对 　　在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数P。 　　示例： 　　输入：[7,5,6,4] 　　输出：5 　　分析问题 　　这道题最容易想到的就是暴力解法，即使用两层for循环，去逐一判断是否构成逆序关系。 　　该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。 　　该算法显然不是最优解，我们第一次听说逆序对的这个概念，应该是在数组排序时。所以，我们这里可以采用归并排序算法来求解逆序对的个数。 　　首先，我们先来回顾一下什么是归并排序。归并排序是分治思想的典型应用，它包含以下三个步骤：分解：假设待排序的区间为[l,r]，我们令mid=(l+r)//2，将区间分成[l,mid]和[mid+1,r]两部分。解决：使用归并排序递归的求解两个子序列，使其有序。合并：把两个已经排好序的子序列[l,mid]和[mid+1,r]合并起来。 　　下面我们来看一下如何使用归并排序来求解逆序对？关键在于归并排序的合并步骤，即利用数组的部分有序性，一下子计算出一个数之前或者之后的逆序数的个数；下面我们来看一个具体的例子，假设目前有两个已经排好序的序列等待合并，分别是L=[8，17，30，45] 和 R=[10，24，27，39]，如下图所示。

　　我们来看一下如何把L、R合并成一个有序的数组。整体思路是将原数组拷贝到辅助数组，再使用双指针法，每次将较小的素归并回去。



　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。 　　16旋转数组 　　问题描述 　　LeetCode189. 旋转数组 　　一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1……An-1 ）变换为（An-m…… An-1 A0 A1……An-m-1）（最后 M 个数循环移至最前面的 M 个位置)。 　　示例： 　　输入：[1,2,3,4,5,6,7] 　　输出：[5,6,7,1,2,3,4] 　　分析问题 　　这道题最直观的想法就是使用额外的数组来将每个素放到正确的位置。我们用n来表示数组的长度，然后遍历原数组，将原数组下标为i的素放至新数组下标为 (i+k) % n 的位置，最后将新数组拷贝到原数组即可。 　　该算法的时间复杂度是O(n)，空间复杂度也是O(n)。但是题目要求不允许使用另外的数组，显然该算法是不符合题意的。我们来观察一下数组移动前后的变化，当我们将数组的素向右移动k次后，尾部 k mod n个素会移动至数组的头部，其余素向后移动k mod n 个位置。因此我们可以采用数组翻转的方法来求解。具体思路如下：首先我们将所有素进行翻转，这样尾部k mod n个素就被移动到数组的头部。然后我们再翻转 [0, (k mod n)-1] 区间的素和 [k mod n, n-1]区间的素，即能得到最后的答案。

　　下面我们来看一下代码的实现。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　17调整数组顺序使奇数位于偶数前面 　　问题描述 　　输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。 　　示例： 　　输入：[1,2,3,4] 　　输出：[1,3,2,4] 　　分析问题 　　这道题我们可以使用双指针法来求解，具体思路如下。首先，申请两个指针i和j，分别指向数组nums的左右两端，即i=0，j=n-1。当i所指的位置为奇数时，执行i=i+1，直到遇到偶数。当j所指的位置为偶数时，执行j=j-1，直到遇到奇数。然后交换nums[i]和nums[j]的值重复上述操作，直到i==j为止。



　　下面我们来看一下代码的实现。 　　其实这道题我们还可以使用快慢指针法来求解，首先我们定义两个指针fast和slow，fast的作用是向前搜索奇数所在的位置，slow的作用是指向下一个奇数应当存放的位置。在fast向前移动的过程中，当它搜索到奇数时，将它和nums[slow]进行交换，然后让slow向前移动一个位置，重复上述操作，直到fast指向数组的末尾为止。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　18矩阵乘法 　　问题描述 　　给定两个n * n 的矩阵A和B，求A * B。 　　示例： 　　输入：[[1,2]，[3,2]]，[[3,4]，[2,1]] 　　输出：[[7,6]，[13,14]] 　　分析问题 　　我们可以使用矩阵乘法规则来求解。对于n * n的矩阵A和矩阵B相乘，所得矩阵C的第i行第j列的素可以表示为Ci,j=Ai,1* B1,j + Ai,2 * B2,j + … + Ai,n * Bn,j , 即等于A的第i行和B的第j列对应素的乘积之和。

　　该算法的时间复杂度是O(N^3)，空间复杂度是O(N^2)。 　　我们都知道对于二维数组来说，在计算机的内存中实际上是顺序存储的，如下所示：

　　因为操作系统加载数据到缓存中时，都是把命中数据附近的一批数据一起加载到缓存中，因为操作系统认为如果一个内存位置被引用了，那么程序很可能在不久的未来引用附近的一个内存位置。所以我们通过调整数组的读取顺序来进行优化，使得矩阵A和B顺序读取，然后相继送入CPU中进行计算，最后使得运行时间能够更快。下面我们来看一下具体做法： 　　该算法的时间复杂度是O(N^3)，但是该算法利用了缓存优化，顺序读取数组A和数组B中的素，因此一般会比第一种方法运行更快。该算法的空间复杂度是O(N^2)。 　　19数字在升序数组中出现的次数 　　问题描述 　　给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数。 　　示例： 　　输入：[1,2,3,3,3,3,4,5],3 　　输出：4 　　分析问题 　　不管数组是否有序，如果要查找数组中是否存在某个素，我们只需要遍历一般数组就好。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　因为题目给定的数组是有序的，所以我们可以使用二分查找来求解。对于有序的数组，如果要寻找的目标值target有多个，那么他们肯定是连在一起的，所以我们可以通过二次二分查找，分别寻找目标值所在范围的上界和下界。首先，我们来看一下上界和下界的定义。下界定义为：如果存在目标值，则指向第一个目标值；如果不存在， 则指向大于目标值的第一个值。上界定义为：不管目标值存在与否，都指向大于目标值的第一个值。

　　下面我们来看一下代码实现。 　　该算法的时间复杂度是O(logN)，空间复杂度是O(1)。 　　20三个数的最大乘积 　　问题描述 　　LeetCode628. 三个数的最大乘积 　　给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。 　　示例： 　　输入：nums = [1,2,3,4] 　　输出：24 　　分析问题 　　数组中三个数的最大乘积有以下二种情况。如果数组中的素全是非负数或者非正数，那么数组中最大的三个数相乘就是最大乘积。如果数组中的素既有正数也有负数，那么最大的乘积既可能是三个最大正数的乘积，也可能是两个最小负数（绝对值最大）和最大正数的乘积。 　　所以，我们只需要找出数组中最大的三个数以及最小的两个数，就可以求得结果。下面我们来看一下如何求解。最容易想到的方式就是先对数组进行降序排序，排好序的数组的前三位以及后两位就是要找的最大的三个数以及最小的两个数。 　　该算法的时间复杂度是O(nlogn)，其中n为数组的长度。排序需要O(nlogn)的时间。 　　空间复杂度是O(logn)，主要是排序的开销。 　　其实我们也可以扫描一遍数组，就可以求出这五个数，如下所示。 　　该算法的时间复杂度是O(n)，空间复杂度是O(1)。 　　21最后 　　原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！ 　　你知道的越多，你的思维越开阔。我们下期再见。