面试高频算法题之数组系列
大家好，我是程序员学长~
今天给大家带来一篇面试高频算法题之数组的详细解析，全文包含19道大厂笔试面试算法真题，一举拿下数组这个知识点，让算法不在成为进入大厂的绊脚石。
如果喜欢，记得点个关注哟~
本文有点长，我已将本文制作成带目录的PDF版本，获取本文PDF版本，请私信我。
最近把面试高频top题都写了一遍，正在逐步整理中，给大家一个算法题的“版本答案”。
全文概览
数组的基础知识
数组的定义及特点
数组是一种线性表数据结构，是在连续内存空间上的存储相同类型数据的集合。
数组主要有以下特点。
- 数组的下标是从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)。
两数之和
问题描述
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
分析问题
拿到这个问题，最简单直观的想法就是对于数组中的每个元素x，去寻找数组中是否存在target-x。
def twoSum(nums, target):
n = len(nums)
for i in range(n):
#对于数组中的每个元素i
#位于它之前的元素都已经和它匹配过了，不需要重复进行匹配
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
我们可以很清楚的知道，这个算法的时间复杂度是O(n^2)。那我们该如何降低时间复杂度呢？可以注意到该算法复杂度高的原因在于寻找元素target-x的时候，需要遍历一遍数组，所以我们需要对这一块进行优化。我们可以采用哈希表，将寻找元素target-x的时间复杂度由O(n)降低到O(1)。
我们在遍历数组时，对于每个元素x，我们首先查询哈希表中是否存在target-x，如果存在，将匹配到的结果直接返回，如果不存在，我们把x插入到哈希表中。
Tips: 我们这里使用字典来代替哈希表，当插入的元素重复时，我们覆盖就好了，这样可以保证查找的时间复杂度为O(1)。为什么这里可以覆盖呢，因为题目要求是找两个数和等于target，当有两个元素重复时，我们认为它们是等价的，所以我们只需要保留一个就好了。
def twoSum(nums, target):
hash_table = dict()
for i, num in enumerate(nums):
if hash_table.__contains__(target-num):
return [hash_table[target - num], i]
hash_table[nums[i]] = i
return []
nums = [2,7,11,15]
target = 9
print(twoSum(nums,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，直接返回。
下面我们来看一下代码的实现。
def twoSum(nums, target):
nums=sorted(nums)
left=0
right=len(nums)-1
while left < right:
sum=nums[left]+nums[right]
if sum>target:
right=right-1
elif sum<target:
left=left+1
else:
return [left,right]
利用sorted进行排序，时间复杂度是O(nlogn)，空间复杂度是O(n)。所以该算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。
最长无重复子数组
问题描述
给定一个数组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。
下面我们来看一下代码如何实现。
if not s:
return 0
left = 0
# 记录每个字符是否出现过
window = set()
n = len(s)
max_len = 0
for i in range(n):
#如果出现过，移除重复元素及其左边的元素
while s[i] in window:
window.remove(s[left])
left += 1
#没出现过，加入window
window.add(s[i])
max_len = max(len(window),max_len)
return max_len
该算法的时间复杂度是O(n)。
合并两个有序数组
问题描述
给你两个按非递减顺序排列的整数数组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进行排序就好了。我们这里就不在赘述。
def merge(nums1, m, nums2, n):
nums1[m:] = nums2
nums1.sort()
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1,m,nums2,n)
print(nums1)
那么既然给定的两个数组是有序的，那我们何不把这个条件利用起来，来优化代码。所以，我们可以使用两个指针p1和p2分别指向两个数组的起始位置，然后比较大小，将较小的放入结果中，然后指针后移，直到将所有元素都排好序。
下面我们来看一下代码的实现。
def merge(nums1, m, nums2, n):
#暂时存放排好序的元素
sorted = []
p1, p2 = 0, 0
#没有遍历完数组时
while p1 < m and p2 < n:
#p1元素遍历完
if nums1[p1] <= nums2[p2]:
sorted.append(nums1[p1])
p1 += 1
else:
sorted.append(nums2[p2])
p2 += 1
if p1 == m:
for x in nums2[p2:]:
sorted.append(x)
else:
for x in nums1[p1:m]:
sorted.append(x)
nums1[:] = sorted
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1,m,nums2,n)
print(nums1)
我们可以知道这里的时间复杂度是O(m+n)，空间复杂度也是O(m+n)。
优化
在使用双指针法时，我们从前往后遍历数组，如果直接使用nums1存储合并结果的话，nums1 中的元素可能会在取出之前被覆盖。所以我们引入了一个临时变量sorted来存储。那有什么办法可以避免nums1中的元素被覆盖呢？既然从前往后不可以，那么我们能从后往前吗？因为nums1的后半部分是空的，可以直接覆盖而不会影响结果，所以这里引入了逆向双指针法。
我们来看一下代码实现。
def merge(nums1, m, nums2, n):
#指向数组的末尾元素
p1 = m -1
p2 = n - 1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
#表示nums1遍历完成
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
#表示nums2遍历完成
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
#将大的元素合并
elif nums1[p1] >= nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
该算法的时间复杂度是O(m+n)，空间复杂度是O(1)。
螺旋矩阵
问题描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
分析问题
题目要求是按照顺时针螺旋顺序输出，即先从左到右、然后从上到下、再从右到左、最后从下到上，依次类推，直到全部元素遍历完为止。在遍历的过程中，最关键的一点就是要记录哪些元素已经被访问过了，如果遇到被访问过的元素，我们就需要顺时针的调整一下方向。
判断元素是否被访问过，最直观的想法就是声明一个和矩阵大小相同的矩阵，来标识矩阵中的元素是否被访问过。
我们来看一下代码如何实现。
def spiralOrder(matrix):
#矩阵为空，直接返回
if not matrix or not matrix[0]:
return []
rows=len(matrix)
columns=len(matrix[0])
visited = [[False for _ in range(columns)] for _ in range(rows)]
#总元素的个数
count=rows*columns
result=[0]*count
#代表方向，即从左到右、从上到下、从右到左、从下到上
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
row, column = 0, 0
#从左上角开始遍历
directionIndex = 0
for i in range(count):
result[i] = matrix[row][column]
#将访问过的元素进行标记
visited[row][column] = True
nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
#不越界，并且已经被访问过了，顺时针调整方向
if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
directionIndex = (directionIndex + 1) % 4
row += directions[directionIndex][0]
column += directions[directionIndex][1]
return result
由于创建了一个和原始矩阵一样大小的矩阵来表示元素是否被访问过，所以该算法的空间复杂度是O(mn)。矩阵中的元素都会被遍历一次，所以该算法的时间复杂度也是O(mn)。
优化
那有什么方法可以优化算法的空间复杂度吗？即我们不用开辟新的空间来保存矩阵中的元素是否被访问过。
其实我们可以在遍历的过程中不断的改变边界条件，当矩阵的第一行元素被访问过之后，那上边界就需要进行+1操作；如果最后一列元素被访问过了，那么右边界需要进行-1操作；如果最后一行元素被访问过了，那下边界需要进行-1操作；如果第一列被访问过了，那需要进行+1操作；依次类推，直到遍历完成。
def spiralOrder(matrix):
# 矩阵为空，直接返回
if not matrix or not matrix[0]:
return []
rows = len(matrix)
columns = len(matrix[0])
result=[]
#开始时，左、右、上、下边界
left=0
right=columns-1
up=0
down=rows-1
while True:
#从左到右
for i in range(left,right+1):
result.append(matrix[up][i])
#上边界调整
up=up+1
#越界，退出
if up>down:
break
#从上到下
for i in range(up,down+1):
result.append(matrix[i][right])
#右边界调整
right=right-1
# 越界，退出
if right<left:
break
#从右到左
for i in range(right,left-1,-1):
result.append(matrix[down][i])
#下边界调整
down=down-1
if down<up:
break
#从下到上
for i in range(down,up-1,-1):
result.append(matrix[i][left])
left=left+1
if left>right:
break
return result
该算法的时间复杂度是O(m*n)，空间复杂度是O(1)。
数组中和为 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]，会导致重复解，所以需要去掉。
我们来看一下代码的实现。
def threeSum(nums):
n=len(nums)
result=[]
if n<3:
return result
nums=sorted(nums)
print(nums)
#遍历数组
for i in range(n):
#固定第一个数
first=nums[i]
#第一个数大于0，由于第二个、第三个数都大于第一个数
#所以不可能相加等于0
if first>0:
break
#已经查找过了，所以不需要再继续寻找，直接跳过
if i>0 and first==nums[i-1]:
continue
#第三个数，开始时指向最数组的最右端
target=-first
right=n-1
left=i+1
while left<right:
if nums[left]+nums[right]==target:
result.append([nums[i],nums[left],nums[right]])
#如果left和left+1对于的元素相同，由于left已经添加到result中了
#为了避免重复，我们跳过相同的元素
while left<right and nums[left]==nums[left+1]:
left=left+1
#同理，跳过和right相同的元素
while left<right and nums[right]==nums[right-1]:
right=right-1
left=left+1
right=right-1
elif nums[left]+nums[right]>target:
right=right-1
else:
left=left+1
return result
nums=[-1,0,1,2,-1,-4]
print(threeSum(nums))
数组中出现次数超过一半的数字
问题描述
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
分析问题
哈希表法
我们最容易想到的方法就是使用哈希表法，去统计每个数字出现的次数，即可很容易的求出众数。
def majorityElement(nums):
#用字典来保存每个数字出现的次数
data_count = {}
for x in nums:
if x in data_count:
data_count[x] = data_count[x] + 1
else:
data_count[x] = 1
max_value=0
max_key=0
#遍历字典，取出次数最大的
#因为题目说给定的数组一定存在众数
#所以最大的次数就是众数
for key in data_count:
value=data_count[key]
if value>max_value:
max_value=value
max_key=key
return max_key
data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
排序算法
我们将数组进行排序，那排序后的数组的中点一定就是众数。
def majorityElement(nums):
#将数组排序
nums.sort()
#返回排序数组中的中点
return nums[len(nums) // 2]
data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))
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时，我们都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数。
class Solution:
def majorityElement(self, nums):
#票数和
counts=0
for num in nums:
#如果票数和为0，我们假设num元素为众数
if counts == 0:
x = num
#如果是众数票数+1，否则票数-1
if num==x:
counts=counts+1
else:
counts=counts-1
return x
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
合并区间
问题描述
以数组 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 中最后一个区间的右端点，将其置为二者的较大值。
这样，我们就可以解决上述的三种情况，下面我们来看一下代码的实现。
class Solution:
def merge(self, intervals):
#将区间数组按照左端点进行升序排序
intervals.sort(key=lambda x: x[0])
#存放合并后的结果
merged = []
for interval in intervals:
#如果列表为空
#或者当前区间的左端点大于merged最后一个元素的右端点，直接添加
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
#否则的话，我们就可以与上一区间进行合并
#修改merged最后一个元素的右端点为两者的最大值
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
该算法的时间复杂度是O(nlogn)，其中n是区间的数量，除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O*(*n logn)。空间复杂度是O(logn)。
在两个长度相等的排序数组中找到上中位数
问题描述
给定两个递增数组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的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组的末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
下面我们来看一下代码如何实现。
class Solution:
def findMedianinTwoSortedAray(self , arr1 , arr2 ):
# write code here
#数组的长度
N=len(arr1)
#定义两个指针，指针两个数组的开始位置
p1=p2=0
ans=0
while p1+p2<N:
#移动较小元素的指针位置
if arr1[p1]<=arr2[p2]:
ans=arr1[p1]
p1=p1+1
else:
ans=arr2[p2]
p2=p2+1
return ans
该算法的时间复杂度是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 小的数。
下面我们来看一个具体的例子。
class Solution:
def findMedianSortedArrays(self, arr1, arr2):
N = len(arr1)
#如果N=1,直接返回两个数组的首元素的最小值即可
if N==1:
return min(arr1[0],arr2[0])
index1, index2 = 0, 0
#中位数位置为N,不过超过分区数组的下标
k=N
while k>1:
new_index1 = index1 + k // 2 - 1
new_index2 = index2 + k // 2 - 1
data1, data2 = arr1[new_index1], arr2[new_index2]
#选择较小值，同时将前k//2个元素删除
if data1 <= data2:
k=k-k//2
#删除前k//2个元素
index1 = new_index1+1
else:
k=k-k//2
#删除前k//2个元素
index2 = new_index2 + 1
return min(arr1[index1],arr2[index2])
加餐
如果给定的两个有序数组大小不同，即给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
根据中位数的定义，当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，我们只需要返回两个数组首元素的最小值即可。
下面我们来看一下代码的实现。
下面我们来看一下代码的实现。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
#获取第k小的元素
def getKthElement(k):
#表示两个有序数组的下标位置
index1, index2 = 0, 0
while True:
#如果一个数组遍历完成，则直接返回另一个数组的第k小元素
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
#如果k为1，返回两个有序数组首元素的最小值
if k == 1:
return min(nums1[index1], nums2[index2])
#防止数组越界，所以取index1 + k // 2 - 1和m - 1的最小值
new_index1 = min(index1 + k // 2 - 1, m - 1)
#同理，取index2 + k // 2 - 1和 n - 1的最小值
new_index2 = min(index2 + k // 2 - 1, n - 1)
data1, data2 = nums1[new_index1], nums2[new_index2]
#如果data1<data2
if data1 <= data2:
#使k的值减少new_index1 - index1 + 1多个元素
k -= new_index1 - index1 + 1
#移除元素
index1 = new_index1 + 1
else:
#使k的值减少new_index2 - index2 + 1多个元素
k -= new_index2 - index2 + 1
#移除元素
index2 = new_index2 + 1
m, n = len(nums1), len(nums2)
#两个数组的长度
lens = m + n
#如果为奇数，则中位数是第(lens+1)/2
#如果为偶数，则中位数是lens/2和lens/2+1的平均值
if lens % 2 == 1:
return getKthElement((lens + 1) // 2)
else:
return (getKthElement(lens // 2) + getKthElement(lens // 2 + 1)) / 2.0
该算法的时间复杂度是O(log(m+n))，空间复杂度是O(1)。
缺失的第一个正整数
问题描述
给你一个无重复元素未排序的整数数组 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。
下面我们来看一下代码实现。
class Solution:
def firstMissingPositive(self, nums):
n = len(nums)
#申请一个临时数组，存放数组中的元素
temp = [0]*n
for i in range(n):
#如果整数不在[1,N]的范围内，不做处理
if nums[i] <= 0 or nums[i] > n:
continue
else:
#否则把整数放入temp的相应位置
temp[nums[i]-1]=nums[i]
#遍历temp,找到第一个不满足temp[i]!=i+1的整数
#就是代表数组中不存在的最小整数
for i in range(n):
if temp[i]!=i+1:
return i+1
#如果都存在，返回N+1
return n+1
我们可以知道该算法的时间复杂度和空间复杂度都是O(n)，显然空间复杂度不满足题目要求，那我们该如何降低算法的空间复杂度呢？通过观察，我们可以发现辅助数组和原数组大小一样，那么我们能否复用原数组nums呢？答案显然是可以的。我们在遍历数组的过程中，假设遍历到的元素值为x，如果x属于[1,N]，我们将元素x和nums[x-1]的元素进行互换，使得x出现在正确的位置上，否则不做处理。当遍历完成后，nums中第一个不满足nums[i-1] = i 条件的就是最小的正整数，如果都满足，那么最小正整数就是N+1。
下面我们来看一下代码的实现。
class Solution:
def firstMissingPositive(self, nums):
#数组的长度
n = len(nums)
#遍历数组，将元素放到正确的位置
for i in range(n):
#如果nums[i]在[1,n]的范围内，并且nums[i]不在正确的位置上，我们进行互换
#否则不做处理
while 1 <= nums[i] <= n \
and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
#找到数组中第一个不满足nums[i] != i + 1条件的
#就是数组中的最小正整数
for i in range(n):
if nums[i] != i + 1:
return i + 1
#如果都满足，最小的整数就是n+1
return n + 1
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
顺时针旋转数组
问题描述
有一个 NxN 整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
要求：时间复杂度O(N^2)，空间复杂度是O(N^2)。
进阶：时间复杂度是O(N^2)，空间复杂度是O(1)
示例：
[ [
[ 5, 1, 9,11], 旋转90度后 [15,13, 2, 5],
[ 2, 4, 8,10], ============> [14, 3, 4, 1],
[13, 3, 6, 7], [12, 6, 8, 9],
[15,14,12,16] [16, 7,10,11]
] ]
分析问题
对于矩阵中的第一行元素来说，在经过90度旋转后，出现在了倒数第一列的位置上，如下图所示。
并且，第一行的第 i 个元素在旋转后恰好是倒数第一列的第 i 个元素。对于第二行的元素也是如此，在旋转后变成倒数第二列的元素，并且第二行的第i个元素在旋转后恰好是倒数第二列的第i个元素。所以，我们可以得出规律，对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置，即对于矩阵中的 matrix[i] [j] 元素，在旋转后，它的新位置为 matrix [j] [n-i-1]。
所以，我们申请一个大小为 n * n 的新矩阵，来临时存储旋转后的结果。我们通过遍历matrix中的所有元素，根据上述规则将元素存放到新矩阵中的对应位置。在遍历完成后，再将新矩阵中复制到原矩阵即可。下面我们来看一下代码实现。
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
#矩阵的大小
n = len(matrix)
#申请一个辅助矩阵
temp = [[0] * n for _ in range(n)]
#遍历矩阵中的所有元素，放到辅助矩阵的相应位置中
for i in range(n):
for j in range(n):
temp[j][n - i - 1] = matrix[i][j]
#将辅助矩阵复制给矩阵
matrix[:] = temp
该算法的时间复杂度是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的矩阵为例，可以按照以下方式划分，进而保证不重复、不遗漏的旋转所有元素。
下面我们来看一下代码的实现。
class Solution(object):
def rotate(self, matrix):
#矩阵的大小
n = len(matrix)
for i in range(n // 2):
for j in range((n + 1) // 2):
#进行一轮原地旋转，旋转4个元素
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = temp
该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。
##数组中的最长连续子序列
问题描述
给定无序数组arr，返回其中最长的连续子序列的长度(要求值连续，位置可以不连续，例如 3,4,5,6为连续的自然数）。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例：
输入：[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。
下面我们来看一下代码的实现。
class Solution:
def longestConsecutive(self, nums):
#记录最长子序列的长度
length = 0
#将数组中的元素放入set中
num_set = set(nums)
for num in num_set:
#判断num-1是否存在于哈希表中，如果存在，直接跳过
if num - 1 not in num_set:
currentdata = num
currentlength = 1
#继续寻找
while currentdata + 1 in num_set:
currentdata += 1
currentlength += 1
#取最大值
length = max(currentlength, length)
return length
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
寻找峰值
问题描述
峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 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。
import random
class Solution:
def findPeakElement(self, nums):
#数组的长度
n = len(nums)
#随机初始化一个位置
idx = random.randint(0, n - 1)
#方便处理nums[-1] 以及 nums[n]的边界情况
def get_value(i):
if i == -1 or i == n:
return float('-inf')
return nums[i]
#当i不是峰值时，如果nums[i] < nums[i+1],此时需要向右走，即i=i+1
#否则需要向左走，即i=i-1
while not (get_value(idx - 1) < get_value(idx) > get_value(idx + 1)):
if get_value(idx) < get_value(idx + 1):
idx = idx + 1
else:
idx = idx - 1
return idx
在最坏的情况下，假设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)。
下面我们来看一下代码的实现。
class Solution:
def findPeakElement(self, nums):
n = len(nums)
# 方便处理 nums[-1] 以及 nums[n] 的边界情况
def get_value(i):
if i == -1 or i == n:
return float('-inf')
return nums[i]
#l,r代表区间的左右边界
l=0
r=n-1
ans=-1
while l <= r:
#取中点
mid = (l + r) // 2
#如果是峰值，直接返回
if get_value(mid - 1) < get_value(mid) > get_value(mid + 1):
ans = mid
break
#如果nums[mid]<nums[mid+1]，代表峰值在[mid+1,r]
#否则在区间[l,mid-1]
if get_value(mid) < get_value(mid + 1):
l = mid + 1
else:
r = mid - 1
return ans
二维数组中的查找
问题描述
LeetCode 剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 matrix 如下：
[
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15]
]
给定 target = 9，返回 true。
给定 target = 20，返回 false。
分析问题
在二维数组中去查找一个元素，我们可以遍历一遍二维数组中的每一个元素，然后去判断是否和目标值相同。该算法的时间复杂度是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。
下面我们来看一下代码的实现。
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m=len(matrix)
#matrix为空时，直接返回False
if m==0:
return False
n=len(matrix[0])
#从左下角开始遍历
i = m - 1
j = 0
while i >= 0 and j <= n - 1:
# 相等返回True
if matrix[i][j] == target:
return True
# 大于向上走
elif matrix[i][j] > target:
i = i - 1
# 小于向右走
elif matrix[i][j] < target:
j = j + 1
return False
该算法的时间复杂度是O(m+n)，空间复杂度是O(1)。
数组中的逆序对
问题描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数P。
示例：
输入：[7,5,6,4]
输出：5
分析问题
这道题最容易想到的就是暴力解法，即使用两层for循环，去逐一判断是否构成逆序关系。
class Solution:
def reversePairs(self, nums) :
n = len(nums)
#如果数组中的元素的个数
# 为0或者1时，表示没有逆序对，直接返回0
if n < 2:
return 0
#逆序对的个数
res = 0
#两层循环去逐一判断是否是逆序对
for i in range(0, n - 1):
for j in range(i + 1, n):
if nums[i] > nums[j]:
res += 1
return res
该算法的时间复杂度是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合并成一个有序的数组。整体思路是将原数组拷贝到辅助数组，再使用双指针法，每次将较小的元素归并回去。
下面我们来看一下代码的实现。
class Solution:
def reversePairs(self, nums) :
n = len(nums)
#数组中个数小于2时，不存在逆序对，所以返回0
if n < 2:
return 0
#用于归并的辅助数组
temp = [0 for _ in range(n)]
return self.reverse_pairs(nums, 0, n - 1, temp)
#归并排序nums
def reverse_pairs(self, nums, left, right, temp):
if left == right:
return 0
mid = (left + right)//2
#将nums分成左、右两部分，递归求解
left_pairs = self.reverse_pairs(nums, left, mid, temp)
right_pairs = self.reverse_pairs(nums, mid + 1, right, temp)
#子序列[left, mid] 和 [mid + 1, right] 已经完成了排序并且计算好逆序对
reverse_pairs = left_pairs + right_pairs
#nums[mid] <= nums[mid + 1]，此时[left，right]已经是有序的了
#所以不存在横跨两个区间的逆序对，直接返回reverse_pairs即可
if nums[mid] <= nums[mid + 1]:
return reverse_pairs
#计算跨两个区间的逆序对
cross_pairs = self.merge_and_count(nums, left, mid, right, temp)
return reverse_pairs + cross_pairs
def merge_and_count(self, nums, left, mid, right, temp):
"""
[left, mid] 有序，[mid + 1, right] 有序，将两个有序的子序列合并成一个有序的子序列
"""
#将nums的元素copy到辅助数组中
for i in range(left, right + 1):
temp[i] = nums[i]
i = left
j = mid + 1
res = 0
for k in range(left, right + 1):
#i>mid,说明left部分已经遍历完，直接将right插入nums
if i > mid:
nums[k] = temp[j]
j += 1
#j>right,说明right部分已经遍历完，直接将left插入nums
elif j > right:
nums[k] = temp[i]
i += 1
# 此时left数组元素小，插入nums中，不计算逆序数
elif temp[i] <= temp[j]:
nums[k] = temp[i]
i += 1
# 此时right数组元素小，插入nums中，统计逆序对，
# 一次可以统计出一个区间的个数的逆序对
else:
nums[k] = temp[j]
j += 1
res += (mid - i + 1)
return res
该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。
旋转数组
问题描述
一个数组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 的位置，最后将新数组拷贝到原数组即可。
class Solution:
def rotate(self,nums,k):
n=len(nums)
tmp=[0]*n
for i in range(0,n):
#将数组nums[i]放到新数组的相应位置
tmp[(i+k)%n]=nums[i]
#将新数组拷贝到原数组
nums[:]=tmp[:]
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。但是题目要求不允许使用另外的数组，显然该算法是不符合题意的。我们来观察一下数组移动前后的变化，当我们将数组的元素向右移动k次后，尾部 k mod n个元素会移动至数组的头部，其余元素向后移动k mod n 个位置。因此我们可以采用数组翻转的方法来求解。具体思路如下：首先我们将所有元素进行翻转，这样尾部k mod n个元素就被移动到数组的头部。然后我们再翻转 [0, (k mod n)-1] 区间的元素和 [k mod n, n-1]区间的元素，即能得到最后的答案。
下面我们来看一下代码的实现。
class Solution:
#对数组中的元素进行翻转
def reverse(self,nums,start,end):
while start < end:
tmp=nums[start]
nums[start]=nums[end]
nums[end]=tmp
start=start+1
end=end-1
def rotate(self,nums,k):
n=len(nums)
k=k%n
#对数组进行反转
self.reverse(nums,0,n-1)
#对区间nums[0,k-1]再进行翻转
self.reverse(nums,0,k-1)
#对区间nums[k,n-1]再进行翻转
self.reverse(nums,k,n-1)
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
调整数组顺序使奇数位于偶数前面
问题描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：[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为止。
下面我们来看一下代码的实现。
class Solution(object):
def exchange(self, nums):
#申请两个变量i和j,开始时，指向数组的两端
i=0
j=len(nums)-1
while i < j:
#从i开始从左向右寻找，直到找到第一个偶数
while i < j and nums[i] % 2 == 1:
i = i + 1
#从j开始从右想左寻找，直到找到第一个奇数
while i < j and nums[j] % 2 == 0:
j = j - 1
nums[i], nums[j] = nums[j], nums[i]
return nums
其实这道题我们还可以使用快慢指针法来求解，首先我们定义两个指针fast和slow，fast的作用是向前搜索奇数所在的位置，slow的作用是指向下一个奇数应当存放的位置。在fast向前移动的过程中，当它搜索到奇数时，将它和nums[slow]进行交换，然后让slow向前移动一个位置，重复上述操作，直到fast指向数组的末尾为止。
class Solution:
def exchange(self, nums):
slow = 0
fast = 0
#循环遍历，直到fast指向nums的末尾
while fast < len(nums):
#如果fast指向奇数，
#交换nums[slow]和nums[fast]
if nums[fast] % 2 == 1:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow=slow+1
fast=fast+1
return nums
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
矩阵乘法
问题描述
给定两个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列对应元素的乘积之和。
class Solution:
def solve(self , a, b):
# write code here
#矩阵a和矩阵b是n*n的矩阵
n=len(a)
res=[[0] * n for _ in range(n)]
for i in range(0,n):
for j in range(0,n):
for k in range(0,n):
#C的第i行第j列的元素为
#A的第i行和B的第j列对应元素乘积的和
res[i][j] += a[i][k]*b[k][j]
return res
该算法的时间复杂度是O(N^3)，空间复杂度是O(N^2)。
我们都知道对于二维数组来说，在计算机的内存中实际上是顺序存储的，如下所示：
因为操作系统加载数据到缓存中时，都是把命中数据附近的一批数据一起加载到缓存中，因为操作系统认为如果一个内存位置被引用了，那么程序很可能在不久的未来引用附近的一个内存位置。所以我们通过调整数组的读取顺序来进行优化，使得矩阵A和B顺序读取，然后相继送入CPU中进行计算，最后使得运行时间能够更快。下面我们来看一下具体做法：
class Solution:
def solve(self , a, b):
# write code here
#矩阵a和矩阵b是n*n的矩阵
n=len(a)
res=[[0] * n for _ in range(n)]
for i in range(0,n):
for j in range(0,n):
#顺序访问矩阵A的元素
temp=a[i][j]
for k in range(0,n):
#矩阵b的元素也是顺序访问的
res[i][k] += temp * b[j][k]
return res
该算法的时间复杂度是O(N^3)，但是该算法利用了缓存优化，顺序读取数组A和数组B中的元素，因此一般会比第一种方法运行更快。该算法的空间复杂度是O(N^2)。
数字在升序数组中出现的次数
问题描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数。
示例：
输入：[1,2,3,3,3,3,4,5],3
输出：4
分析问题
不管数组是否有序，如果要查找数组中是否存在某个元素，我们只需要遍历一般数组就好。
class Solution:
def GetNumberOfK(self,data, k):
n=0
for x in data:
if x==k:
n=n+1
return n
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
因为题目给定的数组是有序的，所以我们可以使用二分查找来求解。对于有序的数组，如果要寻找的目标值target有多个，那么他们肯定是连在一起的，所以我们可以通过二次二分查找，分别寻找目标值所在范围的上界和下界。首先，我们来看一下上界和下界的定义。
- 下界定义为：如果存在目标值，则指向第一个目标值；如果不存在， 则指向大于目标值的第一个值。
- 上界定义为：不管目标值存在与否，都指向大于目标值的第一个值。
下面我们来看一下代码实现。
class Solution:
def GetNumberOfK(self,data, k):
l=0
r=len(data)-1
#二分法寻找下界
while l<r:
mid = (r+l) // 2
if data[mid] < k:
l = mid + 1
else:
r = mid
left=l
#寻找上界
l = 0
r = len(data)-1
while l<r:
mid=(r+l)//2
if data[mid] <= k:
l=mid+1
else:
r=mid
right=l
return right - left
该算法的时间复杂度是O(logN)，空间复杂度是O(1)。
三个数的最大乘积
问题描述
LeetCode628. 三个数的最大乘积
给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。
示例：
输入：nums = [1,2,3,4]
输出：24
分析问题
数组中三个数的最大乘积有以下二种情况。
- 如果数组中的元素全是非负数或者非正数，那么数组中最大的三个数相乘就是最大乘积。
- 如果数组中的元素既有正数也有负数，那么最大的乘积既可能是三个最大正数的乘积，也可能是两个最小负数（绝对值最大）和最大正数的乘积。
所以，我们只需要找出数组中最大的三个数以及最小的两个数，就可以求得结果。下面我们来看一下如何求解。最容易想到的方式就是先对数组进行降序排序，排好序的数组的前三位以及后两位就是要找的最大的三个数以及最小的两个数。
class Solution:
def maximumProduct(self,nums):
nums=sorted(nums)
n=len(nums)
return max(nums[0] * nums[1] * nums[n-1], nums[n - 3] * nums[n - 2] * nums[n-1])
该算法的时间复杂度是O(nlogn)，其中n为数组的长度。排序需要O(nlogn)的时间。
空间复杂度是O(logn)，主要是排序的开销。
其实我们也可以扫描一遍数组，就可以求出这五个数，如下所示。
import sys
class Solution:
def maximumProduct(self,nums):
#最小和第二小
min1=min2=sys.maxsize
#最大、第二大、第三大
max1=max2=max3=-sys.maxsize-1
for x in nums:
if x < min1:
min2=min1
min1=x
elif x<min2:
min2=x
if x>max1:
max3=max2
max2=max1
max1=x
elif x>max2:
max3=max2
max2=x
elif x>max3:
max3=x
return max(max1*max2*max3,max1*min1*min2)
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
最后
原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！
你知道的越多，你的思维越开阔。我们下期再见。
美团公司福利 1420人发布