leetcode1403. 非递增顺序的最小子序列
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例 1：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
来源：力扣（LeetCode）
解题思路关键点：先排序，然后从后到前截取
注意点：（1）for循环的遍历，倒序要到-1值（2）for循环内部的判断条件是：SR<=SL，都要继续
代码如下：
class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
nums.sort()
sum1=sum(nums)
k=len(nums)
tmp=0
sr=0
sl=0
res=[]
for i in range(k-1,-1,-1):
sr=sr+nums[i]
sl=sum1-sr
res.append(nums[i])
if sr<=sl:
continue
else:
break
return res
leetcode:面试题 10.01. 合并排序的数组
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
说明:
A.length == n + m
解题思路关键是：
两路有序数组的归并
代码如下：
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
i=0
j=0
res=[]
k1=len(A)
k2=len(B)
k=k1-k2
while i<k and j<k2:
if A[i]<B[j]:
res.append(A[i])
i=i+1
elif A[i]>B[j]:
res.append(B[j])
j=j+1
else:
res.append(A[i])
res.append(B[j])
i=i+1
j=j+1
if i<k:
for p in range(i,k):
res.append(A[p])
if j<k2:
for p in range(j,k2):
res.append(B[p])
for k in range(k1):
A[k]=res[k]
return
网友评论