文章目录
912. 排序数组
归并
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(nums, l, r):
# 终止条件
if l >= r: return
# 递归划分数组
m = (l + r) // 2
merge_sort(nums, l, m)
merge_sort(nums, m + 1, r)
# 合并子数组
tmp = nums[l:r + 1] # 暂存需合并区间元素
i, j = 0, m - l + 1 # 两指针分别指向左/右子数组的首个元素
for k in range(l, r + 1): # 遍历合并左/右子数组
if i == m - l + 1:
nums[k] = tmp[j]
j += 1
elif j == r - l + 1 or tmp[i] <= tmp[j]:
nums[k] = tmp[i]
i += 1
else:
nums[k] = tmp[j]
j += 1
merge_sort(nums, 0, len(nums)-1)
return nums
总结心得：说实话，一周的时间，我归并排序的思路还记得，但是具体代码怎写，已经忘了80%。看了K神的答案，知道自己现在应该是无法写出来。需要重新自己写一遍，才能记清楚。我连复习都在图快，而不是一个个知识点的过，过完一个，搞懂一个，算一个。人类的天性就是贪多求快，果不其然。我感觉我的意志力和体能都已经快到极限了，今天如果想复习10道题，现在就不可能把归并敲了。所以我决定休息一下，然后明天把归并和快排在写一遍。因为我想，如果面试官问到归并或者快排，绝对不是让我们重新写一个，而是会问我们非常具体的一些细节，如果没理解透彻，很可能栽了。面试的时候，一定有很多细节，如果平时学习或者复习的时候马虎，我就一定去不了最好的公司。这是一定的。你想去最好的公司，你就得付出120%的努力。
快排
def findKthLargest(self, nums: List[int], k: int) -> int:
def quicksort(left, right, nums):
if left >= right: return
pivot = nums[left]
start, end = left, right
while left < right:
while left < right and nums[right] > pivot: right -= 1
while left < right and nums[left] < pivot: left += 1
nums[left], nums[right] = nums[right], nums[left]
nums[left], pivot = pivot, nums[left]
quicksort(start, right-1, nums)
quicksort(left+1, end, nums)
quicksort(0, len(nums)-1, nums)
return nums[-k]
心得总结：今天快排怎么做的，我真的一点都想不起来了。不过现在看了代码已经可以想起来了。明天我打算把全部的排序都仔细再过一遍。
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
que = []
heapq.heapify(que)
for num in nums:
heapq.heappush(que, num)
if len(que) > k:
heapq.heappop(que)
return que[0]
心得总结：之前的代码，我用的方法是快排。这次用的大顶堆，又熟悉了一遍，而且果然速度快好多。
315. 计算右侧小于当前元素的个数
class Solution:
def countSmaller(self, nums) -> List[int]:
def merge(left, right, nums, res, temp, index):
if left >= right: return
mid = (left + right) // 2
merge(0, mid, nums, res, temp, index)
merge(mid+1, right, nums, res, temp, index)
if nums[index[mid]] <= nums[index[mid + 1]]:
return
# 合并
for i in range(left, right + 1):
temp[i] = index[i]
i, j = left, mid - left + 1
for k in range(left, right + 1):
if i > mid:
index[k] = temp[j]
j += 1
elif j > right:
index[k] = temp[i]
i += 1
res[index[k]] += (right - mid)
elif nums[temp[i]] <= nums[temp[j]]:
index[k] = temp[i]
i += 1
res[index[k]] += (j - mid - 1)
else:
index[k] = temp[j]
j += 1
size = len(nums)
if size == 0:
return []
elif size == 1:
return nums[0]
res = [0 for _ in range(size)]
temp = [None for _ in range(size)]
index = [i for i in range(size)]
merge(0, size-1, nums, res, temp, index)
return res
心得总结：这道题是困难题，当时写的时候想起来用逆序对，但是对于索引数组还是不太会用。当时也没搞的太明白，如今依然不会写。看来之前说的是对的，如果没有搞懂，就永远写不出来。参考答案看了好几遍，理解比上一次更深一些了。但是还是无法一口气写出来。
from typing import List
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
size = len(nums)
if size == 0:
return []
if size == 1:
return [0]
temp = [None for _ in range(size)]
res = [0 for _ in range(size)]
# 索引数组，作用：归并回去的时候，方便知道是哪个下标的元素
indexes = [i for i in range(size)]
self.__merge_and_count_smaller(nums, 0, size - 1, temp, indexes, res)
return res
def __merge_and_count_smaller(self, nums, left, right, temp, indexes, res):
if left == right:
return
mid = left + (right - left) // 2
self.__merge_and_count_smaller(nums, left, mid, temp, indexes, res)
self.__merge_and_count_smaller(nums, mid + 1, right, temp, indexes, res)
if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
return
self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)
def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
# [left,mid] 前有序数组
# [mid+1,right] 后有序数组
# 先拷贝，再合并
for i in range(left, right + 1):
temp[i] = indexes[i]
i = left
j = mid + 1
for k in range(left, right + 1):
if i > mid:
indexes[k] = temp[j]
j += 1
elif j > right:
indexes[k] = temp[i]
i += 1
res[indexes[k]] += (right - mid)
elif nums[temp[i]] <= nums[temp[j]]:
indexes[k] = temp[i]
i += 1
res[indexes[k]] += (j - mid - 1)
else:
indexes[k] = temp[j]
j += 1
if __name__ == '__main__':
nums = [5, 2, 6, 1]
solution = Solution()
result = solution.countSmaller(nums)
print(result)
对着答案debug走了一遍，可以看懂，但是在count次数的时候，不是很明白，另外index那里也还是有点懵。先跳过吧。回头再来一遍。
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
def maxSubArray(self, nums: List[int]) -> int:
if not nums: return
if len(nums) == 1: return nums[0]
res, total = [], 0
flag = None
for num in nums:
total += num
if total < 0:
total = 0
continue
else:
flag = True
res.append(total)
return max(res) if flag else max(nums)
这个解法我还记得，应该是简单的动态规划，但是题目说还可以用递归的方法。关于都是负数的情况，我还仔细考虑了一番，如果有一个正数，最后就会返回那个正数。如果都是负数，就会返回负数里最大的，我用了flag作为标记。
递归的方法看了下，没看太懂。
class Solution {
public:
struct Status {
int lSum, rSum, mSum, iSum;
};
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};
Status get(vector<int> &a, int l, int r) {
if (l == r) {
return (Status) {a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);
}
int maxSubArray(vector<int>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};