代码收藏家 python 04 sort
Python 实例教学_ 04_排序
Python 排序
Python 2-04 匿名函数
第一课
3301. 高度互不相同的最大塔高和
class Solution:
def maximumTotalSum(self, maximumHeight: List[int]) -> int:
maximumHeight.sort(reverse = True)
for i in range(1, len(maximumHeight)):
maximumHeight[i] = min(maximumHeight[i], maximumHeight[i - 1] - 1)
if maximumHeight[i] < 1: return -1
return sum(maximumHeight)
2332. 坐上公交的最晚时间
class Solution:
def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
buses.sort()
passengers.sort()
# 模拟乘客上车
j = 0
for t in buses:
c = capacity
while c and j < len(passengers) and passengers[j] <= t:
j += 1
c -= 1
# 寻找插队时机
j -= 1 # 最后一个上车的
res = buses[-1] if c else passengers[j]
while j >= 0 and res == passengers[j]: # 往前找没人到达的时刻
res -= 1
j -= 1
return res
第二课
539. 最小时间差
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
res = inf
timePoints.sort() # 直接排序就可以
t = timePoints[0]
one = pre = int(t[:2]) * 60 + int(t[3:])
for s in timePoints[1:]:
cur = int(s[:2]) * 60 + int(s[3:])
res = min(res, cur - pre)
pre = cur
# 24 * 60 = 1440
return min(res, 1440 - (cur - one))
1005. K 次取反后最大化的数组和
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort()
for i in range(len(nums)):
if nums[i] < 0 and k:
nums[i] = -nums[i]
k -= 1
else:break
# k 为偶数 可能部分负数变正，直接求和
# k 为奇数 全部变正，和减去2倍最小数
return sum(nums) - 2 * min(nums) * (k % 2)
1984. 学生分数的最小差值
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
res = inf
for i in range(len(nums) - k + 1):
res = min(res, nums[i + k - 1] - nums[i])
return res
1200. 最小绝对差
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
arr.sort()
mn, res, n = inf, [], len(arr)
for i in range(1, n):
a, b = arr[i-1], arr[i]
dif = b - a
if dif < mn: # 因为有序， dif >= 0
res = [[a, b]]
mn = dif
elif dif == mn:
res.append([a, b])
return res
第三课
870. 优势洗牌
孙武既死，后百余岁有孙膑。膑生阿、鄄之间，膑亦孙武之后世子孙也。孙膑尝与庞涓俱学兵法。庞涓既事魏，得为惠王将军，而自以为能不及孙膑，乃阴使召孙膑。膑至，庞涓恐其贤于己，疾之，则以法刑断其两足而黥之，欲隐勿见。 齐使者如梁，孙膑以刑徒阴见，说齐使。齐使以为奇，窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远，马有上、中、下、辈。于是孙子谓田忌曰：“君弟重射，臣能令君胜。”田忌信然之，与王及诸公子逐射千金。及临质，“孙子曰：‘今以君之下驷与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。’ 既驰三辈毕，而田忌一不胜而再胜，卒得王千金。
————西汉·司马迁《史记・孙子吴起列传》
nums1 田忌的马，nums2 齐威王的马。
讨论田忌的下等马（nums1 的最小值）：
如果它能比过齐威王的下等马（nums2 的最小值），那这一分田忌直接拿下；
如果它比不过齐威王的下等马，则用田忌的下等马比齐威王的上等马（nums2 的最大值）。
去掉这两匹马，问题变成一个规模更小（n-1）的子问题。重复上述过程，即得到了所有马的对应关系。
代码实现时，由于 nums2 不能排序，可以创建一个下标数组 ids，对 ids 排序，即 ids[0] 对应 nums2 中最小值的下标，ids[1] 对应 nums2 中第二小值的下标，……。用双指针操作 ids，从而知道每个下标所要对应的 nums1 的元素，也就找到了所要求的 nums1 的排列。
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
ans = [0] * n
nums1.sort()
# b = sorted(enumerate(nums2), key=lambda x:x[1])
idx = sorted(range(n), key=lambda i:nums2[i]) # 离线（索引）排序
l, r = 0, n - 1 # 双指针
for x in nums1:
# if x > b[l][1]: # 劣等比劣等，比的过比，赢一局。
# ans[b[l][0]] = x
# l += 1
# else: # 比不过和优等比，放弃一局。
# ans[b[r][0]] = x
# r -= 1
i, j = idx[l], idx[r]
if x > nums2[i]: # 用下等马比下等马
ans[i] = x
l += 1
else: # 用下等马比上等马
ans[j] = x
r -= 1
return ans
905. 按奇偶排序数组
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
ans = [0] * len(nums)
i, j = 0, -1
for x in nums:
if x % 2:
ans[j] = x
j -= 1
else:
ans[i] = x
i += 1
return ans
#return sorted(nums, key=lambda x : x % 2)
922. 按奇偶排序数组 II
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
'''
n, i, j = len(nums), 0, 1
ans = [0] * n
for x in nums:
if x % 2:
ans[j] = x
j += 2
else:
ans[i] = x
i += 2
return ans
'''
n, i, j = len(nums), 0, 1
while i < n - 1 and j < n:
if nums[i] % 2 == 0:
i += 2
if nums[j] % 2:
j += 2
if i < n - 1 and j < n and nums[i] % 2 and nums[j] % 2 == 0:
nums[i], nums[j] = nums[j], nums[i]
i += 2
j += 2
return nums
nums.sort(key=lambda x:x%2)
nums[::2], nums[1::2] = nums[:len(nums)//2], nums[len(nums)//2:]
return nums
1859. 将句子排序
class Solution:
def sortSentence(self, s: str) -> str:
words = s.split()
words.sort(key=lambda w:w[-1])
return ' '.join(word[:-1] for word in words)
第四课
2418. 按身高排序
class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
# return [names[i] for i in sorted(range(len(names)), key=lambda i:heights[i], reverse=True)]
# return [name for _, name in sorted(zip(heights, names), reverse=True)]
return list(zip(*sorted(zip(names, heights), reverse=True, key=lambda x : x[1])))[0]
169. 多数元素
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
cnt, candidate = 0, None
for x in nums:
if cnt == 0: candidate = x
cnt += 1 if x == candidate else -1
return candidate
2231. 按奇偶性交换后的最大数字
class Solution:
def largestInteger(self, num: int) -> int:
a = list(map(int, str(num)))
n = len(a)
# 进行选择排序
for i in range(n - 1):
for j in range(i + 1, n):
if (a[i] - a[j]) % 2 == 0 and a[i] < a[j]:
a[i], a[j] = a[j], a[i]
return int("".join(map(str, a)))
s = str(num)
odd, even = [], []
for x in sorted(s):
if int(x) % 2: odd.append(x)
else: even.append(x)
ans = []
for x in s:
if int(x) % 2: ans.append(odd.pop())
else:ans.append(even.pop())
return int(''.join(ans))
第五课
2164. 对奇偶下标分别排序
class Solution:
def sortEvenOdd(self, nums: List[int]) -> List[int]:
nums[1::2] = sorted(nums[1::2], reverse=True)
nums[0::2] = sorted(nums[0::2])
return nums
2144. 打折购买糖果的最小开销
class Solution:
def minimumCost(self, cost: List[int]) -> int:
# 逆序
cost.sort(reverse = True)
s = sum(cost)
for i in range(2, len(cost), 3):
s -= cost[i]
# 正序
# cost.sort()
# n, s = len(cost), 0
# for i in range(n - 1, -1, -1):
# if (n - i) % 3 != 0: s += cost[i]
return s
# cost.sort(reverse=True)
# return sum(cost) - sum(cost[2::3])
# return sum(cost) - sum(sorted(cost)[2::3])
# return sum(x for i, x in enumerate(sorted(cost, reverse = True)) if i % 3 != 2)
349. 两个数组的交集
350. 两个数组的交集 II
389. 找不同
414. 第三大的数
455. 分发饼干
506. 相对名次
561. 数组拆分
594. 最长和谐子序列
628. 三个数的最大乘积
645. 错误的集合
747. 至少是其他数字两倍的最大数
888. 公平的糖果交换
905. 按奇偶排序数组
922. 按奇偶排序数组 II
940. 不同的子序列 II
976. 三角形的最大周长
977. 有序数组的平方**
1005. K 次取反后最大化的数组和
1030. 距离顺序排列矩阵单元格
1051. 高度检查器
1122. 数组的相对排序
1200. 最小绝对差
1331. 数组序号转换
1337. 矩阵中战斗力最弱的 K 行
1346. 检查整数及其两倍数是否存在
1356. 根据数字二进制下 1 的数目排序
1365. 有多少小于当前数字的数字
1385. 两个数组间的距离值
1403. 非递增顺序的最小子序列
1460. 通过翻转子数组使两个数组相等
1464. 数组中两元素的最大乘积
1491. 去掉最低工资和最高工资后的工资平均值
1502. 判断能否形成等差数列
1608. 特殊数组的特征值
1619. 删除某些元素后的数组均值
1636. 按照频率将数组升序排序
1710. 卡车上的最大单元数
1913. 两个数对之间的最大乘积差
class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
nums.sort()
return nums[-1] * nums[-2] - nums[0] * nums[1]
1984. 学生分数的最小差值
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
# return min(a - b for a, b in zip(nums[k - 1:], nums))
return min(nums[i] - nums[i-k+1] for i in range(k-1, len(nums)))
2037. 使每位学生都有座位的最少移动次数
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
seats.sort()
students.sort()
return sum(abs(a - b) for a, b in zip(seats, students))
2089. 找出数组排序后的目标下标
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
i = bisect_left(nums, target)
j = bisect_right(nums, target)
return list(range(i, j))
2094. 找出 3 位偶数
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
d = Counter(digits)
ans = []
for i in range(100, 1000, 2):
t = Counter([i//100, i//10%10, i%10])
#if not (t - d):
if all(d[x] >= t[x] for x in t):
ans.append(i)
return ans
nums = set()
# 偶数集
even = [(i, x) for i, x in enumerate(digits) if x % 2 == 0]
for i, a in enumerate(digits):
if not a: continue
for j, b in enumerate(digits):
if i == j: continue
for k, c in even:
if j == k or i == k: continue
nums.add(a * 100 + b * 10 + c)
return sorted(nums)
2099. 找到和最大的长度为 K 的子序列
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
a = sorted(enumerate(nums), key=lambda x:x[1])[-k:]
a.sort()
return list(zip(*a))[1]
2148. 元素计数
class Solution:
def countElements(self, nums: List[int]) -> int:
# mx, mn = max(nums), min(nums)
# n = len(nums)
# for x in nums:
# if x in [mx, mn]:
# n -= 1
# return n
i, j, mx, mn = 0, 0, nums[0], nums[0]
# 统计最大值与最小值个数
for x in nums:
if x > mx: i, mx = 1, x
elif x == mx: i += 1
if x < mn: j, mn = 1, x
elif x == mn: j += 1
return len(nums) - i - j if mx != mn else 0
# nums.sort()
# c = Counter(nums)
# return max(len(nums) - c[nums[0]] - c[nums[-1]], 0)
2160. 拆分数位后四位数字的最小和
class Solution:
def minimumSum(self, num: int) -> int:
# d = []
# while num:
# d.append(num % 10)
# num //= 10
# d.sort()
d = sorted(map(int, str(num)))
return 10 * (d[0] + d[1]) + d[2] + d[3]
2273. 移除字母异位词后的结果数组
class Solution:
def removeAnagrams(self, words: List[str]) -> List[str]:
ans = [words[0]]
for w in words:
if sorted(w) != sorted(ans[-1]):
ans.append(w)
return ans
2357. 使数组中所有元素都等于零
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
return len(set(nums) - {0})
2363. 合并相似的物品
class Solution:
def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
d = defaultdict(int)
for k, v in items1:
d[k] += v
for k, v in items2:
d[k] += v
return sorted(d.items())
2389. 和有限的最长子序
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
acc = list(accumulate(sorted(nums)))
ans = []
for x in queries:
ans.append(bisect_right(acc, x))
return ans
LCP 18. 早餐组合
LCP 28. 采购方案
LCP 40. 心算挑战
LCS 02. 完成一半题目
作者：Yake1965
