算法题第三篇 数组
# 数组相关算法
# 无序数组
# 调整数组顺序使得奇数位于偶数前面(剑指offer21)
设置两个指针，偶数就删除插入尾部，奇数不做处理
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
l=0
h=len(nums)
while l < h:
if nums[l] % 2 == 0:
nums.append(nums.pop(l))
h-=1
else:
l+=1
return nums
2
3
4
5
6
7
8
9
10
11
# 移动零 283
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
如，输入：[0,1,0,3,12]
输出：[1,3,12,0,0]
注意：不拷贝额外的数组，减少操作次数
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
i = 0
for num in nums:
if num != 0:
nums[i] = num
i += 1
for j in xrange(i, len(nums)):
nums[j] = 0
2
3
4
5
6
7
8
9
# 两数之和
# 三数之和(15)
给你一个包含n个整数的数组nums，判断nums中是否存在三个元素，使得这三个整数相加为0
例：输入:nums = [-1,0,1,2,-1,-4]
输出：[-1,-1,2],[-1,0,1]
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
seen = set()
n = len(nums)
for i in range(n):
a = nums[i]
if a in seen:
continue
seen.add()
d = {}
for j in range(i+1,n):
b = nums[j]
if b in d and (not(ans) or (ans[-1][0]!= a or ans[-1][2] != b)):
ans.append((a,-a-b,b))
else:
d[-a-b] = 0
return ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 最接近的三数之和16
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
nearest = 10 ** 7
for i in range(n - 2):
lo, hi = i + 1, n - 1
# 双指针
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total == target:
return total
elif total < target:
lo += 1
else:
hi -= 1
# 直接根据"最近"的定义取结果
nearest = min(nearest, total, key=lambda x: abs(x - target))
return nearest
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
两个数组的交集
给定两个数组，编写算法计算他们的交集
例：输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
inter = set(nums1) & set(nums2)
l = []
for i in inter:
l += [i] * min(nums1.count(i), nums2.count(i))
return l
2
3
4
5
6
7
8
9
10
11
12
# 四数之和18
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：
0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。
例：输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue
for k in range(i+1, n):
if k > i + 1 and nums[k] == nums[k-1]: continue
p = k + 1
q = n - 1
while p < q:
if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
else:
res.append([nums[i], nums[k], nums[p], nums[q]])
while p < q and nums[p] == nums[p + 1]: p += 1
while p < q and nums[q] == nums[q - 1]: q -= 1
p += 1
q -= 1
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 无序整数数组，找出第k大的值215
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。、
例：输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if len(nums) == 1: return nums[0]
mid = int(len(nums) // 2)
left, right, mids = [], [], []
for i in range(len(nums)):
if nums[i] > nums[mid]:
left.append(nums[i])
elif nums[i] < nums[mid]:
right.append(nums[i])
else:
mids.append(nums[i])
if len(left) >= k:
return self.findKthLargest(left, k)
elif len(mids) >= k - len(left):
return nums[mid]
else:
return self.findKthLargest(right, k - len(left) - len(mids))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 买卖股票的最佳时机1、2、3、4(121,122,123,188,309)
给定数组prices，第i个元素表示股票第i天的价格
需选择在某一天买入，并在某一天卖出，设计一个算法计算获取的最大利润
例：输入：[7,1,5,3,6,4]
输出：5 在第二天买入，第5天卖出，6-1=5
class Solution:
def maxProfit(self,prices:List[int])-> int:
min_p,max_v = float('inf'),0
for p in prices:
min_p = min(min_p,p)
max_v = max(max_v,p-min_p)
return max_v
2
3
4
5
6
7
122给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
贪心
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
ans += prices[i] - prices[i-1]
return ans
2
3
4
5
6
7
dp
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0]*2 for _ in range(n)]
# dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
dp[0][0], dp[0][1] = 0, - prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
return dp[n-1][0]
2
3
4
5
6
7
8
9
10
11
12
123:给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [0] * 5
dp[1] = -prices[0]
dp[3] = -prices[0]
for i in range(1, len(prices)):
dp[1] = max(dp[1], dp[0] - prices[i])
dp[2] = max(dp[2], dp[1] + prices[i])
dp[3] = max(dp[3], dp[2] - prices[i])
dp[4] = max(dp[4], dp[3] + prices[i])
return dp[4]
2
3
4
5
6
7
8
9
10
11
12
13
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * (2*k+1) for _ in range(len(prices))]
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
for i in range(1, len(prices)):
for j in range(0, 2*k-1, 2):
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
return dp[-1][2*k]
2
3
4
5
6
7
8
9
10
11
12
309:给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0:
return 0
dp = [[0] * 4 for _ in range(n)]
dp[0][0] = -prices[0] #持股票
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][3])
dp[i][2] = dp[i-1][0] + prices[i]
dp[i][3] = dp[i-1][2]
return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])
2
3
4
5
6
7
8
9
10
11
12
13
# 连续子数组最大和(53)
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
例：输入：nums = [-2,1,-3,4,-1,2,1-5,4]
输出：6，连续子数组[4,-1,2,1]的和最大，为6
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i]= nums[i] + max(nums[i-1], 0)
return max(nums)
2
3
4
5
# 乘积最大子数组(152)
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
例：输入：[2,3,-2,4]
输出：6
class Solution:
def maxProduct(self, nums: List[int]) -> int:
B = nums[::-1]
for i in range(1, len(nums)):
nums[i] *= nums[i - 1] or 1
B[i] *= B[i - 1] or 1
return max(max(nums),max(B))
2
3
4
5
6
7
# 组合、组合总和1、2、3（77、39、40、216）
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
例：输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtrack(n, k, StartIndex):
if len(path) == k:
res.append(path[:])
return
for i in range(StartIndex, n-(k-len(path)) + 2):
path.append(i)
backtrack(n, k, i+1)
path.pop()
backtrack(n, k, 1)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
例：输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]]
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def helper(i, tmp_sum, tmp):
if tmp_sum > target or i == n:
return
if tmp_sum == target:
res.append(tmp)
return
helper(i, tmp_sum + candidates[i],tmp + [candidates[i]])
helper(i+1, tmp_sum ,tmp)
helper(0, 0, [])
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
40:
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
例：输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
candidates.sort()
n = len(candidates)
res = []
def backtrack(i, tmp_sum, tmp_list):
if tmp_sum == target:
res.append(tmp_list)
return
for j in range(i, n):
if tmp_sum + candidates[j] > target : break
if j > i and candidates[j] == candidates[j-1]:continue
backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])
backtrack(0, 0, [])
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
组合总和3
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。 解集不能包含重复的组合。
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = [] #存放结果集
path = [] #符合条件的结果
def findallPath(n,k,sum,startIndex):
if sum > n: return #剪枝操作
if sum == n and len(path) == k: #如果path.size() == k 但sum != n 直接返回
return res.append(path[:])
for i in range(startIndex,9-(k-len(path))+2): #剪枝操作
path.append(i)
sum += i
findallPath(n,k,sum,i+1) #注意i+1调整startIndex
sum -= i #回溯
path.pop() #回溯
findallPath(n,k,0,1)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 全排列(46、47)
46:给一个不含重复数组，返回其所有可能的全排列
输入:[1,2,3]
输出:[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
class Solution:
def permute(self,nums:List[int])->List[List[int]]:
res = []
def backtrack(nums,tmp):
if not nums:
res.append(tmp)
return
for i in range(len(nums)):
backtrack(nums[:i]+nums[i+1],tmp+[nums[i]])
backtrack(nums,[])
return res
2
3
4
5
6
7
8
9
10
11
47:给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2];
输出： [[1,1,2], [1,2,1], [2,1,1]]
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# res用来存放结果
if not nums: return []
res = []
used = [0] * len(nums)
def backtracking(nums, used, path):
# 终止条件
if len(path) == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
if not used[i]:
if i>0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = 1
path.append(nums[i])
backtracking(nums, used, path)
path.pop()
used[i] = 0
# 记得给nums排序
backtracking(sorted(nums),used,[])
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 子集78、90
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(nums,startIndex):
res.append(path[:]) #收集子集，要放在终止添加的上面，否则会漏掉自己
for i in range(startIndex,len(nums)): #当startIndex已经大于数组的长度了，就终止了，for循环本来也结束了，所以不需要终止条件
path.append(nums[i])
backtrack(nums,i+1) #递归
path.pop() #回溯
backtrack(nums,0)
return res
2
3
4
5
6
7
8
9
10
11
12
90:给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = [] #存放符合条件结果的集合
path = [] #用来存放符合条件结果
def backtrack(nums,startIndex):
res.append(path[:])
for i in range(startIndex,len(nums)):
if i > startIndex and nums[i] == nums[i - 1]: #我们要对同一树层使用过的元素进行跳过
continue
path.append(nums[i])
backtrack(nums,i+1) #递归
path.pop() #回溯
nums = sorted(nums) #去重需要排序
backtrack(nums,0)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 移除元素(27)
给出一个数组和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的长度
例：输入：nums = [3,2,2,3] val= 3
输出：2,nums = [2,2]
快慢指针
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
2
3
4
5
6
7
8
# 下一个排列(31)
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
例：输入 nums = [1,2,3]。这个数是123，找出1，2，3这3个数字排序可能的所有数，排序后，比123大的那个数 也就是132
输入 nums = [3,2,1]。这就是1，2，3所有排序中最大的那个数，那么就返回1，2，3排序后所有数中最小的那个，也就是1，2，3 -> [1,2,3]
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
# i<0时已经为最大的排列
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
l = nums[i+1:]
l.reverse()
nums[i+1:] = l
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 旋转数组(189)
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
class Solution:
def rotate(self, nums:List[int], k:int)-> None:
nums[: ] = (nums[i] for i in range(-(k % len(nums)),len(nums)-k % len(nums)))
2
3
# 最长连续递增子序列(300)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
例如：输入：[10,9,2,5,3,7,101,18]
输出：4 ，最长递增子序列为[2,5,7,101]
输入：[0,1,0,3,2,3]
输出：4，最长递增子序列为[0,1,2,3]
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1 for _ in range(n)]
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
2
3
4
5
6
7
8
9
# 连续子数组的最大和(剑指offer42)
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0], max_sum = nums[0], nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
max_sum = max(max_sum, dp[i])
return max_sum
2
3
4
5
6
7
8
# 数组拼接最小数
# 只出现过一次的数字(136)
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
例：输入：[2,2,1]
输出：1
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a = 0
for num in nums:
a = a ^ num
return a
2
3
4
5
6
# 只出现过一次的数字2(137)
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
例：输入：[2,2,3,2]
输出：3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(0,len(nums)-3,3):
if nums[i]!=nums[i+1]:
return nums[i]
return nums[-1]
2
3
4
5
6
7
# 缺失的第一个正数(41)
给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数
例：输入：[1,2,0]
输出:4
class Solutioon:
def firstMissingPositive(self,nums:List[int])-> int:
nums = set(nums)
for j in range(1, 2 ** 31 - 1):
if j not in nums:
return j
2
3
4
5
6
# 颜色分类(75)
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
例：输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
快排
class Solution:
def sortColors(self, nums: List[int]) -> None:
2
3
# 柱状图中最大的矩形(84)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入: [2,1,5,6,2,3] 输出: 10
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans, s, hs = 0, [0], [0, *heights, 0]
for i, h in enumerate(hs):
while hs[s[-1]] > h:
ans = max(ans, (i - s[-2] - 1) * hs[s.pop()])
s.append(i)
return ans
2
3
4
5
6
7
8
# 长度最小的子数组(209)
给定一个含有n个正整数和一个正整数target
找出该数组中满足其和大于target的长度最小的连续子数组，并返回其长度
例：nums=[2,3,1,2,4,3], target=7
输出：2
class Solution:
def minSubArrayLen(self, target:int,nums: List[int])-> int:
i, ans = 0, len(A) + 1
for j in range(len(A)):
s -= A[j]
while s <= 0:
ans = min(ans,j-i+1)
s += A[i]
i += 1
return ans % (len(A)+1)
2
3
4
5
6
7
8
9
10
# 存在重复元素(217)
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
例：输入：[1,2,3,1]
输出：true
输入：[1,2,3,4]
输出：false
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return not (len(nums)==len(set(nums)))
2
3
# 存在重复元素2(219)
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
例：输入：nums = [1,2,3,1], k = 3
输出：true
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
nums_len = len(nums)
if nums_len <= 1:
return False
nums_dict = {}
for i in range(nums_len):
if nums[i] in nums_dict:
if i-nums_dict[nums[i]] <= k:
return True
nums_dict[nums[i]] = i
return False
2
3
4
5
6
7
8
9
10
11
12
# 存在重复元素3（220）
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
例：输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
ls = [[nums[i], i] for i in range(len(nums))]
ls.sort(key=lambda x: x[0])
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if ls[j][0] - ls[i][0] > t:
break
if abs(ls[j][1] - ls[i][1]) <= k:
return True
return False
2
3
4
5
6
7
8
9
10
11
# 寻找重复数字287
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
例：输入：nums = [1,3,4,2,2] 输出：2
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
lo, hi = 1, len(nums)-1
while lo < hi:
mid = (lo + hi) // 2
if sum(i<=mid for i in nums) <= mid:
lo = mid + 1
else:
hi = mid
return lo
2
3
4
5
6
7
8
9
10
# 数组中重复的数据(442)
给定一个整数数组a，其中有些元素出现了两次而有些元素出现了一次，找出所有出现两次的元素
输入：[4,3,2,7,8,2,3,1]
输出：[2,3]
class Solution:
def findDuplicates(self, nums:List[int])-> List[int]:
res = []
for x in nums:
if nums[abs(x-1)] < 0:
res.append(abs(x))
else:
nums[abs(x)-1] *= -1
return res
2
3
4
5
6
7
8
9
# 寻找峰值162
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
例：输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo < hi:
mid = (lo+hi) // 2
mid2 = mid + 1
if nums[mid] < nums[mid2]:
lo = mid2
else:
hi = mid
return lo
2
3
4
5
6
7
8
9
10
11
# 多数元素(169)
波义尔摩尔投票算法
def majorityElement(self, nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
2
3
4
5
6
7
8
# 求众数(229)
给定一个大小为n的整数组，找出其中所有出现超过n/3次的元素
输入：[3,2,3]
输出：[3]
class Solution:
def majorityElement(self, nums:List[int]) -> Lisr[int]:
count1, count2, candidate1, candidate2 = 0,0,0,1
for n in nums:
if n == candidate1:
count1 += 1
elif n == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = n,1
elif count2 == 0:
candidate2, count2 = n,1
else:
count1, count2 = count1 - 1,count2 - 1
return [n for n in (candidate1,candidate2)
if nums.count(n) > len(nums) // 3]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 有序数组
# 在排序数组中查找元素的第一个和最后一个位置34
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
例：输入：nums = [5,,7,7,8,8,10],target = 8
输出：[3,4]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = [-1, -1]
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2 # 向左取整
if nums[mid] < target: # 首先考虑一定不存在解的区间，则有+1（或者-1）
l = mid + 1
else:
r = mid
if not nums or nums[l] != target: # 用例中有nums = [] 的情况
return res
res[0] = l
l, r = r, len(nums) - 1
while l < r:
mid = l + (r - l + 1) // 2 # 向右取整
if nums[mid] > target:
r = mid - 1
else:
l = mid
res[1] = r
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 搜索插入位置35
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
例：输入:[1,3,5,6],5
输出：2
输入：[1,3,5,6],2
输出：1
二分法查找
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
low = 0
high = len(nums)
while low < high:
mid = low + (high - low)//2
if nums[mid] > target:
high = mid
elif nums[mid] < target:
low = mid +1
else:
return mid
return low
2
3
4
5
6
7
8
9
10
11
12
13
# 合并区间(56)
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
例：输入：[1,3],[2,6],[8,10],[15,18]
输出：[1,6],[8,10],[15,18]
先排序，然后判断是否合并区间
class Solution:
def merge(self,intervals:List[List[int]])->List[List[int]]:
if intervals == []:
return []
intervals.sort(key = lambda x:x[0])
##前一个合并区间
pre = intervals[0]
res = []
for i in range(1,len(intervals)):
if intervals[i][0] <= pre[1]:
##合并，更新pre结束位置
if intervals[i][1] > pre[1]:
pre[1] = intervals[i][1]
else
res.append(pre)
pre = intervals[i]
##最后一个没有加进去
res.append(pre)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 插入区间(57)
给你一个 无重叠的 *，*按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠
例：输入：intervals = [1,3],[6,9],newInterval = [2,5]
输出：[[1,5],[6,9]]
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
intervals = sorted(intervals, key=lambda x: x[0])
merge = [intervals[0]]
for i in range(1, len(intervals)):
mergeleft = merge[-1][0]
mergeright = merge[-1][1]
interleft = intervals[i][0]
interright = intervals[i][1]
if interleft > mergeright:
merge.append(intervals[i])
else:
merge[-1][1] = max(mergeright, interright)
return merge
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 删除有序数组的重复项(26)
删除有序数组中重复的元素，在原数组上进行操作，
def removeDuplicates(nums):
if not nums:
return 0
index = 1
for i in range(len(nums)-1):
if nums[i] != nums[i+1]:
nums[index] = nums[i+1]
index +=1
return index
2
3
4
5
6
7
8
9
# 删除有序数组的重复项2(80)
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
例：输入：[1,1,1,2,2,3]
输出：[1,1,2,2,3]
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for e in nums:
if i < 2 or e != nums[i - 2]:
nums[i] = e
i += 1
return i
2
3
4
5
6
7
8
9
# 合并排序数组(88)
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, k = m-1, n-1, m+n-1
while i >=0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 汇总区间(228)
给定一个无重复元素的有序整数数组，返回恰好覆盖数组中所有数组的最小有序区间范围列表，
例：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
class Solution:
def summaryRange(self, nums: List[int]) -> List[str]:
li = []
i = 0
while i < len(nums):
j = i + 1;
while j < len(nums) and nums[j] == nums[i] + j - i:
j += 1
li.append(str(nums[i]) if i == j-1 else str(nums[i]) + '->' + str(nums[j-1]))
i = j
return li
2
3
4
5
6
7
8
9
10
11
# 寻找右区间436
给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
例：输入：intervals = [[1,2]] 输出：[-1] 解释：集合中只有一个区间，所以输出-1。
输入：intervals = [[3,4],[2,3],[1,2]] 输出：[-1, 0, 1] 解释：对于 [3,4] ，没有满足条件的“右侧”区间。 对于 [2,3] ，区间[3,4]具有最小的“右”起点，在原数组中索引为0; 对于 [1,2] ，区间[2,3]具有最小的“右”起点，在原数组中索引为1。
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
n = len(intervals)
res = [-1] * n
dic = {}
for i, v in enumerate(intervals):
dic[v[0]] = i
start = sorted(dic.keys())
for i, v in enumerate(intervals):
l, r = 0, n - 1
while l <= r:
mid = (l + r) >> 1
if v[1] > start[mid]:
l = mid + 1
else:
r = mid - 1
if l < n:
res[i] = dic[start[l]]
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 和为s的连续正数序列(剑指offer57)
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
例：输入：target = 9
输出：[[2,3,4],[4,5]]
双指针滑动窗口
class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
n = target//2+1
nums = list(range(1,n+1))
left,right = 0,0
sums,res = 0,[]
while right<len(nums):
sums+=nums[right]
right+=1
while sums>=target:
if sums==target:
res.append(nums[left:right])
sums-=nums[left]
left+=1
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 多维数组
# 最大正方形(221)
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
例：输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == '1':
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
return max(map(max, dp)) ** 2
2
3
4
5
6
7
8
9
10
11
# 最大矩形(85)
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
例：输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0:
return 0
res = 0
m, n = len(matrix), len(matrix[0])
heights = [0] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == '0':
heights[j] = 0
else:
heights[j] = heights[j] + 1
res = max(res, self.largestRectangleArea(heights))
return res
def largestRectangleArea(self, heights):
heights.append(0)
stack = []
res = 0
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
s = stack.pop()
res = max(res, heights[s] * ((i - stack[-1] - 1) if stack else i))
stack.append(i)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 单词搜索(79)
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
l,w = len(board),len(board[0])
l_word = len(word)
def dfs(a,b,index,hel):
if a<0 or b<0 or a>=l or b>=w or board[a][b]!=word[index] or (a,b) in hel:
return False
elif board[a][b]==word[index] and index==len(word)-1:
return True
return dfs(a+1,b,index+1,hel+[(a,b)]) or dfs(a-1,b,index+1,hel+[(a,b)]) or dfs(a,b+1,index+1,hel+[(a,b)]) or dfs(a,b-1,index+1,hel+[(a,b)])
for i in range(l):
for j in range(w):
if board[i][j] == word[0]:
if dfs(i,j,0,[]):
return True
return False
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 岛屿数量
深度优先与广度优先都可以。DFS（深度优先搜索）：
从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点
BFS（广度优先搜索）：从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个顶点
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or len(grid) == 'o': return 0
row, columns = len(grid), len(grid[0])
count = 0
for i in range(row):
for j in range(columns):
if grid[i][j] == '1':
self.dfs(grid, i, j, row, columns)
count += 1
return count
def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
grid[i][j] = '0'
self.dfs(grid, i - 1, j, row, columns)
self.dfs(grid, i, j - 1, row, columns)
self.dfs(grid, i + 1, j, row, columns)
self.dfs(grid, i, j + 1, row, columns)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 岛屿最大面积
class Solution:
def helper(self,grid,i,j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]==0:
return 0
grid[i][j]=0
count=1
tmp = [[1,0],[-1,0],[0,1],[0,-1]]
for x,y in tmp:
dx = x+i
dy = y+j
count+=self.helper(grid,dx,dy)
return count
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
tmp = self.helper(grid,i,j)
res = max(tmp,res)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 三角形路径之和(120)
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
例：输入：[[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11，2--3--5--1
实例
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
#自底向上
dp = triangle
m = len(triangle)
for i in range(m-1,-1,-1):
if i<m-1:
for j in range(len(triangle[i])):
dp[i][j] += min(dp[i+1][j],dp[i+1][j+1])
return dp[0][0]
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
#自底向上
dp = triangle[-1]
m = len(triangle)
for i in range(m-1,-1,-1):
if i<m-1:
for j in range(len(triangle[i])):
dp[j] = min(dp[j],dp[j+1]) + triangle[i][j]
return dp[0]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 顺时针打印数组(54，剑指offer29)
给你一个m*n的矩阵，请按照顺时针螺旋顺序，打印矩阵中的所有元素
如：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
思路： 取首行，去除首行后，对矩阵翻转来创建新的矩阵， 再递归直到新矩阵为[],退出并将取到的数据返回
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
ret = []
if matrix == []:
return ret
ret.extend(matrix[0]) # 上侧
new = [reversed(i) for i in matrix[1:]]
if new == []:
return ret
r = self.spiralOrder([i for i in zip(*new)])
ret.extend(r)
return ret
2
3
4
5
6
7
8
9
10
11
12
# 顺时针生成数组(59)
def generateMatrix(self,n: int) -> List[List[int]]:
ans = [[0]*n for _ in range(n)]
op = itertools.cycle([(0,1),(1,0),(0,-1),(-1,0)])
d = next(op)
x,y = [0,0]
for k = range(1,n**2+1):
ans[x][y] = k
i,j = x+d[0], y+d[1]
if not 0<= i < n or not 0<=j<n or ans[i][j]:
d = next(op)
x,y = x+d[0], y+d[1]
else:
x,y = i,j
return ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 有序矩阵中第 K 小的元素378
给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出：13 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
lo, hi = matrix[0][0], matrix[-1][-1]
while lo < hi:
mid = (lo + hi) // 2
if sum(bisect.bisect(row, mid) for row in matrix) < k:
lo = mid + 1
else:
hi = mid
return lo
2
3
4
5
6
7
8
9
10
# 旋转数组
# 搜索旋转排序数组目标值33、81
旋转有序数组是分段有序的，给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。
例：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
class Solution:
def search(self,nums,target):
lo,hi = 0,len(nums)-1
while lo < hi:
mid = (lo + hi)//2
if(nums[0] > target) ^ (nums[0]>nums[mid]) ^ (target>nums[mid]):
lo = mid + 1
else
hi = mid
return lo if lo == hi and target == nums[lo] else -1
2
3
4
5
6
7
8
9
10
81:如果数组中有重复元素，编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
class Solution:
def search(self, nums: List[int], target: int) -> bool:
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo+hi) >> 1
if nums[mid] == target:
return True
while lo<mid and nums[lo]==nums[mid]:
lo += 1
if nums[lo] <= nums[mid]: # 左侧有序
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # 右侧有序，因为下落点在左侧
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 搜索旋转排序数组最小值153、154
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
class Solution:
def findMin(self,nums:List[int])->int:
lo,hi=0,len(nums)-1
while lo < li:
mid = (lo+li)//2
if(nums[mid]) > nums[hi]:
lo = mid + 1
elif nums[mid] == nums[hi]:
hi -=1
else
hi = mid
return nums[lo]
2
3
4
5
6
7
8
9
10
11
12
如果数组中有重复元素，
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo < hi:
mid = (lo+hi) >> 1
if nums[mid] > nums[hi]:
lo = mid + 1
elif nums[mid] < nums[hi]:
hi = mid
else:
hi -= 1
return nums[lo]
2
3
4
5
6
7
8
9
10
11
12