1. 开始时2不在窗口中，所以扩大窗口。

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

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

4. 下一个元素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

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)

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[:] = sortednums1 = [1,2,3,0,0,0] m = 3 nums2 = [2,5,6] n = 3 merge(nums1,m,nums2,n) print(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

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) % 4row += directions[directionIndex][0] column += directions[directionIndex][1] return result

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 rightright: break return result

1. 当nums[first]=nums[first-1]，由于我们已经把第一个元素是nums[first-1]的三元组已经求解过了，所以没必要重复求解。
2. 当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 lefttarget: right=right-1 else: left=left+1 return resultnums=[-1,0,1,2,-1,-4] print(threeSum(nums))

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=https://www.it610.com/article/0 max_key=0 #遍历字典，取出次数最大的 #因为题目说给定的数组一定存在众数 #所以最大的次数就是众数 for key in data_count: value=data_count[key] if value>max_value: max_value=https://www.it610.com/article/value max_key=key return max_keydata=https://www.it610.com/article/[1,2,3,2,2,2,5,4,2] print(majorityElement(data))

def majorityElement(nums): #将数组排序 nums.sort() #返回排序数组中的中点 return nums[len(nums) // 2]data=https://www.it610.com/article/[1,2,3,2,2,2,5,4,2] print(majorityElement(data))

1. 当n1等于x时，抵消的所有数字中，有一半是众数x。
2. 当n1不等于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

• 如果当前区间的左端点在数组 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

class Solution: def findMedianinTwoSortedAray(self , arr1 , arr2 ): # write code here #数组的长度 N=len(arr1) #定义两个指针，指针两个数组的开始位置 p1=p2=0 ans=0 while p1+p2

该算法的时间复杂度是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 + 1return 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

该算法的时间复杂度是O(log(m+n))，空间复杂度是O(1)。
缺失的第一个正整数 问题描述
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。

文章图片


文章图片


文章图片

下面我们来看一下代码实现。

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)。
顺时针旋转数组 问题描述
LeetCode 面试题 01.07. 旋转矩阵
有一个 NxN 整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
要求：时间复杂度O(N2)，空间复杂度是O(N2)。
进阶：时间复杂度是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(N2)，空间复杂度O(N2)。
进阶
那我们如何在不使用辅助空间的情况下，实现矩阵的原地旋转呢？我们来看一下方法一中为什么要引入辅助空间，对于matrix中的元素，我们使用公式temp[j] [n - i - 1] = matrix[i] [j]进行旋转，如果不申请辅助矩阵，我们直接把元素 matrix[i] [j]，放到矩阵 matrix[j] [n - i - 1]位置，原矩阵中的matrix[j] [n - i - 1]元素就被覆盖了，这显然不是我们要的结果。

文章图片


文章图片


文章图片

当知道了如何原地旋转矩阵之后，这里还有一点需要明确：我们应该选取哪些位置进行上述的原地交换操作呢？通过上面的分析可以知道，一次可以原地交换四个位置，所以：

1. 当n为偶数时，我们需要选取 n^2 / 4 = (n/2) * (n/2)个元素进行原地交换操作，可以将该图形分为四块，可以保证不重复、不遗漏旋转所有元素；
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)。
数组中的最长连续子序列 问题描述
LeetCode128. 最长连续序列
给定无序数组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 = https://www.it610.com/article/num currentlength = 1 #继续寻找 while currentdata + 1 in num_set: currentdata += 1 currentlength += 1 #取最大值 length = max(currentlength, length)return length

该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
寻找峰值 问题描述
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。

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 - 1return 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。

1. 取区间[l，r]的中点，即mid=(l+r)/2。
2. 如果下标mid是峰值，直接返回。
3. 如果nums[mid] < nums[mid+1]，表示峰值在mid的右边，所以抛弃区间[l，mid]，在剩余的[mid+1，r]的区间内去寻找。
4. 如果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]

二维数组中的查找 问题描述
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)。
数组中的逆序对 问题描述
LeetCode 剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数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)。
该算法显然不是最优解，我们第一次听说逆序对的这个概念，应该是在数组排序时。所以，我们这里可以采用归并排序算法来求解逆序对的个数。
首先，我们先来回顾一下什么是归并排序。归并排序是分治思想的典型应用，它包含以下三个步骤：

1. 分解：假设待排序的区间为[l,r]，我们令mid=(l+r)//2，将区间分成[l,mid]和[mid+1,r]两部分。
2. 解决：使用归并排序递归的求解两个子序列，使其有序。
3. 合并：把两个已经排好序的子序列[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_pairsdef 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)。
旋转数组 问题描述
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 的位置，最后将新数组拷贝到原数组即可。

class Solution: def rotate(self,nums,k): n=len(nums) tmp=[0]*nfor 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]
分析问题
这道题我们可以使用双指针法来求解，具体思路如下。

1. 首先，申请两个指针i和j，分别指向数组nums的左右两端，即i=0，j=n-1。
2. 当i所指的位置为奇数时，执行i=i+1，直到遇到偶数。
3. 当j所指的位置为偶数时，执行j=j-1，直到遇到奇数。
4. 然后交换nums[i]和nums[j]的值
5. 重复上述操作，直到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(N3)，空间复杂度是O(N2)。
我们都知道对于二维数组来说，在计算机的内存中实际上是顺序存储的，如下所示：

文章图片

因为操作系统加载数据到缓存中时，都是把命中数据附近的一批数据一起加载到缓存中，因为操作系统认为如果一个内存位置被引用了，那么程序很可能在不久的未来引用附近的一个内存位置。所以我们通过调整数组的读取顺序来进行优化，使得矩阵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(N3)，但是该算法利用了缓存优化，顺序读取数组A和数组B中的元素，因此一般会比第一种方法运行更快。该算法的空间复杂度是O(N2)。
数字在升序数组中出现的次数 问题描述
给定一个长度为 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

该算法的时间复杂度是O(logN)，空间复杂度是O(1)。
三个数的最大乘积 问题描述
LeetCode628. 三个数的最大乘积 给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。
示例：
输入：nums = [1,2,3,4]
输出：24
分析问题
数组中三个数的最大乘积有以下二种情况。

1. 如果数组中的元素全是非负数或者非正数，那么数组中最大的三个数相乘就是最大乘积。
2. 如果数组中的元素既有正数也有负数，那么最大的乘积既可能是三个最大正数的乘积，也可能是两个最小负数（绝对值最大）和最大正数的乘积。

所以，我们只需要找出数组中最大的三个数以及最小的两个数，就可以求得结果。下面我们来看一下如何求解。最容易想到的方式就是先对数组进行降序排序，排好序的数组的前三位以及后两位就是要找的最大的三个数以及最小的两个数。

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 xmax1: max3=max2 max2=max1 max1=x elif x>max2: max3=max2 max2=x elif x>max3: max3=xreturn max(max1*max2*max3,max1*min1*min2)

该算法的时间复杂度是O(n)，空间复杂度是O(1)。
最后 原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！
你知道的越多，你的思维越开阔。我们下期再见。

推荐阅读

• 

  大衬衣怎么搭配 让人眼前一亮
• 

  玻璃胶如何使用？玻璃胶如何使用?
• 

  橙子是什么季节的水果 怎么挑选橙子
• 

  华为手机忘记锁屏密码怎么办
• 

  如何快速升级公益服务器？ 公益服务器怎么升级最快
• 

  苹果动图如何保存 苹果怎么保存贴吧动图
• 

  志高空调无法开机该怎么解决?,基本上用这几种方法
• 

  国庆节购车指南 2020国庆节买车优惠力度大吗
• 

  立式空调怎么消毒
• 

  华为S7703交换机,一个镜像口如何对应多个观察口？华为S7703的介绍
• 

  灵芝孢子粉怎么吃
• 

  linux的echo命令 linux中echo命令的用法
• 

  李白的《清平调》是李白最有意境的诗吗？
• 

  最新版excel怎么制作迷你图 excel2016怎么添加迷你图
• 

  湖北荆州一周天气预报_湖北荆州天气查询
• 

  新款混动汉兰达报价及图片 新款汉兰达混动版落地多少钱
• 

  驱动桥类型 驱动桥类型有哪几种
• 

  文明6全面开战神级难度教学 全面开战怎么玩
• 

  玩咖女是什么意思
• 

  android中shape 的使用

• 画解算法（1.|画解算法：1. 两数之和）
• Guava|Guava RateLimiter与限流算法
• 一个选择排序算法
• SG平滑轨迹算法的原理和实现
• 《算法》-图[有向图]
• LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
• 虚拟DOM-Diff算法详解
• 《数据结构与算法之美》——队列
• 算法回顾（SVD在协同过滤推荐系统中的应用）
• 简谈迪克斯特拉算法