前言滑窗算法常用于序列的连续子序列的处理。通过两个指针维护一个窗口，通过一些逻辑对这个窗口——亦即一个连续的子序列——进行处理。简单的例子：最长无公共字母的子串这道题可以通过LeetCode 3访问，一个AC解是：class Solution: def lengthOfLongestSubstring(self, s: str) -> int: d = {} res = 0 l, r = 0, 0 while r < len(s): while l < r and s[r] in d: d.pop(s[l]) l += 1 d[s[r]] = 1 res = max(r-l+1, res) r += 1 return res这道题通过左右指针+哈希表的结构维护一个区间，哈希表记录这个区间内的字母的出现次数。右指针不断移动，迭代每一个字母，如果右指针的移动带来了字母的重复，就移动左指针，直到没有重复字母为止。滑窗算法的步骤通常是：编写维护连续区间的逻辑：这要求预先判断出，题目涉及到连续子序列的操作，可以通过滑窗求解。具体考虑时，需要考虑该怎么维护，单纯的滑窗？滑窗加上一些外部数据结构？迭代过程的处理：思考边界条件是什么？两个指针在什么条件下移动？简单的例子：模式串的排列匹配这道题可以通过LeetCode 567访问，一个AC解是：class Solution: def isSameDict(self, d1, d2): if len(d1) != len(d2): return False for k1 in d1.keys(): if k1 not in d2: return False if d2[k1] != d1[k1]: return False return True def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False d1, d2 = {}, {} for c1 in s1: if c1 in d1: d1[c1] += 1 else: d1[c1] = 1 l, r = 0, len(s1) - 1 for idx in range(r+1): c2 = s2[idx] if c2 in d2: d2[c2] += 1 else: d2[c2] = 1 while r < len(s2): if self.isSameDict(d1, d2): return True if d2[s2[l]] == 1: d2.pop(s2[l]) else: d2[s2[l]] -= 1 l += 1 r += 1 if r == len(s2): break if s2[r] in d2: d2[s2[r]] += 1 else: d2[s2[r]] = 1 return False这道题通过滑窗+哈希表的结构维护区间内部的信息。通过题干，很容易发现是连续序列的处理，那么字母的排列不会影响长度，就代表滑窗的窗口大小固定了。依次迭代，发现字母出现的次数与模式串一致，就代表匹配成功了。简单的例子：替换后可出现的最长单字母串这道题可通过LeetCode 424访问，一个AC解是：class Solution: def getMinDiffCharTime(self, d): if len(d) <= 1: return 0 maxi = 0 total = 0 for v in d.values(): maxi = max(maxi, v) total += v return total - maxi def characterReplacement(self, s: str, k: int) -> int: d = {} l = 0 result = 0 for r in range(len(s)): d[s[r]] = d[s[r]] + 1 if s[r] in d else 1 while l < r and self.getMinDiffCharTime(d) > k: if d[s[l]] == 1: d.pop(s[l]) else: d[s[l]] -= 1 l += 1 result = max(result, r-l+1) return result这道题的答案我并没有优化，完全可以通过定长list优化哈希表。不过，这道题依然是通过哈希表+滑窗进行序列的维护。
前言链表是一个不常使用在日常软件开发中的数据结构，但是，却经常会被用于出算法题，这是因为，链表的两个元素之间是通过next指针相连，如果没有维护好这个指针信息，就会导致无法访问到某一元素。我们一般使用单向链表，其中每个元素的结构包括一个data变量和一个next指针，前者用于存储数据，后者用于记录下一个元素的地址，C语言的表示为：typedef struct LinkedListNode { int data; struct LinkedListNode* next; } LLN;简单的例子：反转链表这道题可以通过LeetCode 206访问，这道题的一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(head == NULL || head->next == NULL) { return head; } struct ListNode* prev = NULL; struct ListNode* curr = head; struct ListNode* neno = head->next; while(curr != NULL) { //neno = curr->next; curr->next = prev; prev = curr; curr = neno; neno = (neno == NULL) ? NULL : neno->next; } return prev; }在循环内，neno的赋值选择注释掉的一行还是未注释的一行都可以。只涉及$O(1)$空间复杂度的链表反转，重要之处在于如何维护next节点的信息。因为，当反转链表时，由于next指向的问题，如果不维护下一个节点的信息，那么下一次迭代就没有办法访问了。所以这道题的逻辑是这样的：下一个节点的维护：记录当前节点的下一个节点。主要逻辑：反转当前节点的下一节点指向。为下一次迭代做准备：即prev和curr节点的赋值。只要是涉及链表的算法，最重要的就是如何维护下一个节点的信息。简单的例子：合并两个排好序的链表这道题可以通过LeetCode 21访问，这道题的一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)); head->val = 0; head->next = NULL; struct ListNode* curr = head; struct ListNode* p1 = list1; struct ListNode* p2 = list2; while(p1 != NULL || p2 != NULL) { if(p2 == NULL) { curr->next = p1; p1 = p1->next; } else if(p1 == NULL) { curr->next = p2; p2 = p2->next; } else { if(p1->val >= p2->val) { curr->next = p2; p2 = p2->next; } else { curr->next = p1; p1 = p1->next; } } curr = curr->next; } return head->next; }值得注意的是，我不推荐任何人使用C去进行LeetCode的作答，比如malloc后的赋值操作，对于算法没有任何影响，但是删除这两句，便无法AC。这道题就很好体现了我们之前说的三个步骤：下一个节点的维护：划分不同条件，根据空指针、值大小判断当前节点接续什么节点。主要逻辑：接续的过程。为下一次迭代做准备：将curr节点变作它的下一个节点。中等的例子：快慢指针这道题可以通过LeetCode 141访问，一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(head == nullptr) { return false; } ListNode* slowp = head, *fastp = head->next; while(slowp != fastp) { if(fastp == nullptr || fastp->next == nullptr) { return false; } slowp = slowp->next; fastp = fastp->next->next; } return true; } };这道题的关键在于，一个链表如果有环，那么迭代将永远无法遇到空指针，并且利用不同速度迭代，将会相遇。那么，我们可以让一个指针走得快一些，一个指针慢一些，如果遇到了空指针，就是无环，如果相遇了就是有环。这道题同样是三个步骤：下一个节点的维护：确定快慢指针的落点。主要逻辑：是否遇到空指针？是否快慢指针相遇？为下一次迭代做准备。中等的例子：链表的重排这道题可以通过LeetCode 143访问，一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { ListNode* curr = head; vector<ListNode*> v; while(curr != nullptr) { v.push_back(curr); curr = curr->next; } curr = head; for(int i = 0; i < v.size() / 2; ++i) { if(i != 0) { curr->next = v[i]; curr = curr->next; } curr->next = v[v.size() - i - 1]; curr = curr->next; } if(v.size() % 2 == 1) { curr->next = v[v.size() / 2]; curr = curr->next; } curr->next = nullptr; } };这道题的重要之处在于后续节点的处理，尤其是最后一行——最后一个节点的next节点要清空。其实这道题本身不难，只是最后一行的curr->next=nullptr;如果没有想到，会花掉大量的调试时间。中等的例子：深度拷贝链表这道题可以通过LeetCode 138访问，一个AC解是：/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { unordered_map<Node*, Node*> um; Node* curr = head; while(curr != nullptr) { Node* copy = (Node*)malloc(sizeof(Node)); copy->val = curr->val; copy->next = nullptr; copy->random = nullptr; um.insert({curr, copy}); curr = curr->next; } curr = head; while(curr != nullptr) { um[curr]->next = um[curr->next]; um[curr]->random = um[curr->random]; curr = curr->next; } return um[head]; } };这道题的重要之处在于，通过一种连接索引关系，恢复另一种索引关系。先根据next深度拷贝每个节点，然后根据next节点的索引关系恢复random节点。
前言双指针是一种用于解决区间问题的算法，这类算法通常的复杂度都是$\Theta(n)$。其实，我们可以将二分看作一种特殊的双指针，每次筛选掉一半的数据。同样的，双指针也可以看作一种特殊的二分，只不过每次通常筛选掉一个数据。简单的例子：回文串的判断这道题可以通过LeetCode 125访问，这道题的一个AC解是：class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: while not (s[left].isalpha() or s[left].isnumeric()) and left < right: left += 1 while not (s[right].isalpha() or s[right].isnumeric()) and left < right: right -= 1 if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True这道题的思想很简单，每次判断左右两个字符，如果一致，就左指针右移一位，右指针左移一位，判断下一个字符。这道题体现了双指针的基本写法，在区间上，首先将指针置于左右两侧，然后进行必要的操作，随后移动两个指针（或某一个指针），满足$O(n)$的复杂度。双指针算法的重要之处在于指针的移动方法。简单的例子：二和问题这道题可以通过LeetCode 167访问，这道题的一个AC解是：class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left, right = 0, len(numbers) - 1 while left < right: curr_sum = numbers[left] + numbers[right] if curr_sum < target: left += 1 elif curr_sum > target: right -= 1 else: return [left+1, right+1]由于这道题已经排好序了，所以我们完全可以应用双指针算法来解决这个问题，左右指针对着的值相加，然后判断这个值的大小，如果这个值过大了，证明我们需要缩小，就将右指针左移；如果值太小，就要左指针右移。这里是双指针的一个另一个特点——它对具有一定单调性的区间效果很好。对于回文串，这个单调性是通过回文串的性质来体现的，即每个字母只和中央对称过去的字母有关。在这道题中，由于序列排好序了，那么通过指针移动的方向，就能够判断出指针所指向值的和的变化方式。中等的例子：接雨水青春版这道题可以通过LeetCode 11访问，这道题的一个AC解是：class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height)-1 result = 0 while l < r: result = max(result, min(height[r], height[l]) * (r-l)) if height[l] == height[r]: l += 1 r -= 1 elif height[l] < height[r]: l += 1 else: r -= 1 return result这道题的单调性就没有那么显然——是通过接雨水的原理体现的。接雨水需要两个边，这两个边之中的最小值为实际的接雨水的高，宽则是两个边的“横坐标”之差。此外，由于左右指针是从外向内收缩的，那么接雨水的宽是单调递减的。那么，当我们双指针指向两条边的时候，其中对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的。这个时候需要长边指针向内收。这个说法一定正确吗？我们来证明一下，最开始假设：两条指针指向的边长度为$d_1, d_2$，坐标为$x_1, x_2$，那么假设二者中间有一条更长或者更短的边，其长度为$d$，坐标为$x$，那么它所参与的左右两个容器的容积分别为$(x-x_1)\min(d,d_1)$和$(x_2-x)\min(d,d_2)$，我们知道：$$ (x-x_1)<x_2-x_1,(x_2-x)<x_2-x_1 $$并且左、右边容器的高最高分别也就是$d_1$和$d_2$，所以左右两个容器的容积必然小于总容积，那么“对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的”这句话是成立的。随着指针变化，又会怎么变化呢？其实，结论也是成立的，因为挪动的指针指向的边，是较短边，这条边的最大雨水容量已经找出来了，就没必要继续考虑了。这便是这道题单调性的来源。中等的例子：三和问题这道题可以通过LeetCode 15访问，一个AC解是：class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() l, r, m = 0, len(nums) - 1, 1 result = [] for i in range(len(nums)): if i > 0 and nums[i] == nums[i-1]: continue l, r = i+1, len(nums) - 1 while l < r: curr_val = nums[l] + nums[r] if curr_val == -nums[i]: result.append([nums[i], nums[l], nums[r]]) l += 1 while nums[l] == nums[l - 1] and l < r: l += 1 elif curr_val > -nums[i]: r -= 1 else: l += 1 return result这道题的解法是，首先创造单调性——排序。然后通过定一议二的方法利用双指针求解。这道题的难度在于不是那么好想出来“排序-迭代-双指针”的解法。困难的例子：接雨水这道题可以通过LeetCode 42访问，一个AC解是：class Solution: def trap(self, height: List[int]) -> int: l, r = 0, len(height) - 1 left_max, right_max = 0, 0 water = 0 while l < r: if height[l] < height[r]: if height[l] >= left_max: left_max = height[l] else: water += left_max - height[l] l += 1 else: if height[r] >= right_max: right_max = height[r] else: water += right_max - height[r] r -= 1 return water这个解是我复制粘贴得来的，并非我自己手搓的。这道题我更习惯于单调栈的解法。这道题的关键在于，明白接雨水的原理——一个容器是由短边控制的。我们首先从左右两边向中间迭代，如果右边有比左边高的边，那么左边这条边一定能形成一个以这条边为短边的容器，在左侧边和右侧边中间的点，其高度往上，一定能形成一个小水洼，水的高度为left_max-height[l]。这道题的单调性在哪里？其实，这道题的单调性就在于，一个容器的高度变化是——先递减再递增的。
前言分治法的通用步骤是：划分-求解-合并。将一个比较大的问题拆分成若干小问题，然后分别求解。分治法和动态规划的区别在于，分治法通常求解子问题之间彼此独立的场景，而动态规划用于求解子问题之间不独立的场景。这一区别将在动态规划一节中阐述。分治法最常用的算法为二分法，也就是将问题分割为两个子问题，分别求解之后进行合并。简单的例子：归并排序用Python语言的归并排序实现如下所示：def merge_sort(arr): if len(arr) <= 1: return arr divide_point = len(arr) // 2 left = merge_sort(arr[:divide_point]) right = merge_sort(arr[divide_point:]) return merge(left, right) def merge(left_arr, right_arr): result = [] while len(left_arr) > 0 and len(right_arr) > 0: if left_arr[0] < right_arr[0]: result.append(left_arr.pop(0)) else: result.append(right_arr.pop(0)) while len(left_arr) > 0: result.append(left_arr.pop(0)) while len(right_arr) > 0: result.append(right_arr.pop(0)) return result if __name__ == "__main__": arr1 = [1,2,3,4,5,6,7,8,9] arr2 = [9,8,7,6,5,4,3,2,1] arr3 = [1,3,5,7,9,2,4,6,8] print(merge_sort(arr1)) print(merge_sort(arr2)) print(merge_sort(arr3))其中，merge_sort函数控制着整个排序过程，在这个过程中，首先将待排序的list对半分，分为两个部分，分别对左右两个部分排序后，再进行合并操作。合并操作的过程受merge函数控制。如您所见，分治算法的划分过程，是将大问题（排序整个list）分割为不相关的小问题（排序左右两个list，且这两个排序过程彼此独立），求解的过程，是处理最小的、能够直接解决的小问题（当分割的list中只有一个元素）的过程，合并的过程，则是对子问题进行综合处理，得到大问题的解（将两个排好序的list合并）。“在写分治算法的过程时，不要过度关心分解该怎么做，而是关心该如何分解”。这是一个非常微妙的描述，更具体来说，就是不要关心分解之后的问题经历了什么，而是要关心如何分割问题，分治算法的关键在于最小问题的处理方法以及合并的方法。简单的例子：二分查找基础二分查找一个更能分治法的算法是二分查找，二分查找的目的是在给定一个排好序的序列中，寻找到想要的值的下标。这个算法的复杂度达到了惊人的$\Theta(\log n)$。这个算法通过对半划分，每次查找能筛选掉一半的候选项，所以这个算法的复杂度实际上是$\Theta(\log_2n)$。一个Python实现如下：if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 4 left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: print(mid) break elif arr[mid] < target: left = mid + 1 else: right = mid - 1这个函数的划分方式不如归并排序那样清晰，不过我们能够从循环中能看出来：每次搜索，首先判断数列中间的值，如果这个值比目标值大，那么就表明，中间这个值在目标值的右边，就搜索中间值左边的子数列；如果这个值比目标值小，那么就表明，中间这个值在目标值的左边，就搜索中间值右边的子数列。这里，值得注意的是while left <= right这句代码。这一行代码中的=体现了分治算法中，考虑“最小问题的处理方法”的重要性。添加了一个等号，就表明数列没有元素时，也要进行判断，这个时候判断的是left和right同时指向的位置的值。如果不加=，那么算法需要被改写：if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 4 left = 0 right = len(arr) - 1 while left < right: mid = (left + right) // 2 if arr[mid] == target: print(mid) break elif arr[mid] < target: left = mid + 1 else: right = mid - 1 # New Stuff. You can also replace left with right. if arr[left] == target: print(left)这个时候，最后需要判断left和right指向的值的大小。简单的变体：算术平方根的计算这个问题可以通过Leetcode 69访问。这个问题的一个AC解是：class Solution: def mySqrt(self, x: int) -> int: left, right = 0, x while left <= right: mid = (left + right) // 2 mid_res = mid * mid if mid_res < x: left = mid + 1 elif mid_res > x: right = mid - 1 else: return mid return left - 1这个算法的重点是最后一行的left - 1是什么意思，更大一点说，二分查找最后左右指针指向的位置代表什么。其实，最后一行也可以换为return right，当我们找不到目标值时，left和right会指向离目标值最近的点，left会指向比这个值大的点，而right会指向比这个值小的点。我们做一个不那么严谨的数学推导，来证明最后一次二分运算时，就是left==right的情况。假设原来的序列长度是$k$，序列从1开始计数，那么每次筛选掉的元素有多少？通过上面的例子我们知道，中间点的坐标是$[\frac{k}{2}]$，中间点及其某一侧的点全被舍弃，那么舍弃的长度$\text{DiscardLength}$以及余下的长度$\text{LeftLength}$就是：$$ \text{DiscardLength}(k)=[\frac{k+1}{2}] $$$$ \text{LeftLength}(k)=k-\text{DiscardLength}(k) $$当然，如果$k$是奇数，那么有$\text{DiscardLength}(k)=\frac{k+1}{2}$，可以推得：$$ \text{LeftLength}(k)=2n+1-\frac{2n+2}{2}=n $$如果是偶数，那么有$\text{DiscardLength}(k)=\frac{k}{2}$，可以推得：$$ \text{LeftLength}(k)=2n-n=n $$易知$n=[\frac{k}{2}]$，我们知道$[\frac{k}{2}]\leq \frac{k}{2}$，那么最后的长度总不会大于$\frac{k}{2^n}$，而我们知道：$$ \lim_{n\to\infty}\frac{k}{2^n}=0 $$那么，最后的结果就是，left和right指向同一个地方（它们之间有0个元素）。在这个时候，再经历一次二分运算，中间值便是这两个指针指向的位置，这个时候，如果中间值比目标值小，那么左指针右移，符合我们的预期，反之就右指针左移。最终都是left会指向比这个值大的点，而right会指向比这个值小的点。那么回看问题，我们的目标是求得目标数字算术平方根的整数部分，显然要找小于这个点的值。就是右指针指向的位置。中等的变体：有规律而非排好序的二分查找这个问题可以通过Leetcode 162访问。这个问题的一个AC解是：class Solution: def findPeakElement(self, nums: List[int]) -> int: if len(nums) == 1: return 0 left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if mid == 0: if nums[mid] > nums[mid+1]: return mid else: left = mid + 1 elif mid == len(nums) - 1: if nums[mid] > nums[mid-1]: return mid else: right = mid - 1 else: if nums[mid-1] < nums[mid] and nums[mid+1] < nums[mid]: return mid elif nums[mid-1] > nums[mid]: right = mid - 1 else: left = mid + 1 这道题中，数列并没有排好序，但是这不影响我们用二分查找，这便是二分查找的一种推广——只要问题中能够筛选一半的数据，就可以使用二分查找。中等的例子：最邻近点距这个问题的描述很简单：在一个二维平面上，有$n$个点，寻找到欧几里得距离最近的两个点。如果直接穷举，那么复杂度将是$O(n\times (n-1)!)$。第一个$n$是计算每个点对欧几里得距离的开销，后面一项则是每个点的计算次数。但是，通过分治算法，我们可以把复杂度降到$O(n\log n)$。既然说到分治法，那么第一步肯定就是分割，首先将所有点按照横坐标/纵坐标排序，然后按照中间横坐标点进行分割，分割为左右两边，一直分割到最后只有两个点。这一步的复杂度受排序复杂度为主导，而排序的复杂度显然是$O(n\log n)$。求解过程，就是求左右两个子集内部的最邻近点距，记作$d_1,d_2$，其中假设$d_1>d_2$，令$d=\min(d_1,d_2)$。合并过程则tricky一些，通过划分-求解过程，我们求到了两个子集内部的最邻近点距，但是两个子集之间呢？我们以划分点为中心，左右各划出$d$的空间。对于纵坐标，我们只考虑划分点上下各$d$的空间，这是一个正方形的空间，边长为$d$。这个空间内，最大有6个点。我们可以将这个空间分割为若干底边为$\frac{d}{2}$，高边为$\frac{2d}{3}$的矩形，每个矩形里只能有一个点，否则根据容斥原理，$d=\frac{5d}{6}$。到此，这个算法分析完了，其复杂度为$O(n\log n)$。中等的例子：求两个排好序的数列的中位数这个问题可以通过Leetcode 4访问。这个问题的一个AC解是：class Solution: def solve(self, nums1, nums2, target_idx): left1, right1 = 0, len(nums1) - 1 left2, right2 = 0, len(nums2) - 1 while True: if left1 > right1: return nums2[target_idx - left1] if left2 > right2: return nums1[target_idx - left2] mid_idx1, mid_idx2 = (left1 + right1) // 2, (left2 + right2) // 2 mid_val1, mid_val2 = nums1[mid_idx1], nums2[mid_idx2] if mid_idx1 + mid_idx2 < target_idx: if mid_val1 >= mid_val2: left2 = mid_idx2 + 1 elif mid_val1 < mid_val2: left1 = mid_idx1 + 1 else: if mid_val1 >= mid_val2: right1 = mid_idx1 - 1 else: right2 = mid_idx2 - 1 def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: mid_val = (len(nums1) + len(nums2)) // 2 if (len(nums1) + len(nums2)) % 2 == 1: return self.solve(nums1, nums2, mid_val) else: return (self.solve(nums1, nums2, mid_val) + self.solve(nums1, nums2, mid_val-1)) / 2.这道题的重点在于分割的方式，对于总长的奇偶性的分割，这里不再赘述。主要来看一下solve函数的解法。为了求解中位数，那么我们筛去的长度$\text{FilteredLength}$必然为：$$ \text{FilteredLength}=\frac{\text{ArrayLength}_1+\text{ArrayLength}_2}{2} $$其中，$\text{ArrayLength}_1$代表nums1的元素个数。那么，这种情况，我们就可以应用二分法，每次迭代来合理地筛选掉一部分元素。当然可以通过在两个数列内分别二分，最后合并的方法来求解。首先，我们可以考虑一下两个数列到底有哪些可能性：nums1的最大值小于nums2的最小值，即$[1,2,3]$和$[4,5,6]$。nums1和nums2有一部分交集，比如$[1,3,5]$和$[2,4,6]$。nums1的最小值大于nums2的最大值，即$[4,5,6]$和$[1,2,3]$。我们首先来考虑情况1和3，并且两个数列之间的长度差异很大，那么中位数必然落在某一个数列的中间。假设我们已经知道了合并方法，那么在二分的时候，长度小的数列，其必然会被完全筛选掉，而筛选掉的情况便是左指针大于右指针的值，那么这个时候，只需要考虑一个数列即可。那么我们来讨论最为困难的情况——两个数列需要合并的情况。这个情况又可以分为两类，即筛选多于整体一半和筛选少于整体一半的情况。这里的筛选是指筛选掉小于中位数的数字。如果筛选多了，就要调节右指针，让整体往值较小的方向靠近；如果筛选少了，就要调节左指针，让整体往值较大的方向靠近。值得注意的是，如果筛选掉的值正正好好，那么我们需要调节右指针，避免出现筛选过量的情况。
前言本系列记录我对于各种算法的理解。本篇改自我本科课程“算法设计与分析”的笔记。本篇不通过例子讨论具体的算法。算法复杂度分析的数学工具算法是为了解决问题而生的，它必须有这样几个性质：可终止、有确定性、正确性、有输入/输出。算法的复杂度分析通常从两个方面来入手——时间复杂度分析和空间复杂度分析。时间复杂度分析通常以操作的个数衡量。对于一个特定的输入来说，算法的时间复杂性是对该输入产生结果所需要的原子操作数。一个算法的时间复杂度是关于输入大小的函数，记作$T(n)$，其中$n$是输入的大小。空间复杂度分析通常以占据的存储空间大小来衡量。对于一个特定的输入来说，算法的空间复杂度是该算法对该输入产生结果所需要的存储空间大小，记作$S(n)$。接下来我们来讨论一下分析复杂性的工具，其实用于分析的基本工具很简单，只有这么几个：同阶函数集合、低阶函数集合、高阶函数集合和严格低/高阶函数。对于同阶函数来说，最重要的是观察函数的主导项，比如$f(x)=x^2+3x+4$这个函数，其同阶函数集合就可以表示为$\Theta(n^2)$，因为这个函数的主要增长项是$x^2$，这个时候，要忽略低阶项和常系数。一个形式化的表达是：$$ \Theta(g(n))=\\{f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\leq f(n) \leq c_2g(n) \\} $$低阶函数集合用于描述一个函数的上界，用$O(n)$格式来表示，其形式化定义是：$$ O(g(n))=\\{f(n)|\exists c>0, n_0, \forall n>n_0, 0\leq f(n)\leq cg(n)\\} $$高阶函数集合用于描述一个函数的下届，在算法领域，用于描述最优情况的复杂度，用$\Omega(n)$的格式来表示。在这个基础上，我们有一个重要的分析工具——递归方程。比如对于归并排序，就有如下的公式：$$ T(1)=O(1) $$$$ T(n)=2T(\frac{1}{2}n)+O(n) $$这个时候，我们该如何求得$T(n)$的同阶函数集合呢？完全可以用迭代法，也就是通过数列迭代的基本关系求解，比如：$$ T(n)=2T(\frac{1}{2}n)+cn=4T(\frac{1}{4}n)+2cn=\cdots $$由此可见，这个公式的结构是：$$ T(n)=2^kT(\frac{1}{2^k}n)+kcn $$当$\frac{1}{2^k}n=1$时，有$k=\log_2n$，这个时候有：$$ T(n)=n+cn\log_2n $$由此可知，$T(n)=\Theta(n\log n)$。当然，也可以用主定理来快速求解，主定理的内容是，当递归方程形式为$T(n)=aT(\frac{n}{b})+f(n)$且$a\geq 1,b>1$时，若：存在$\epsilon>0$，有$f(n)=O(n^{\log_ba-\epsilon})$，则$T(n)=\Theta(n^{\log_ba})$。存在$\epsilon\geq0$，有$f(n)=\Theta(n^{\log_ba}\log^\epsilon n)$，则$T(n)=\Theta(n^{\log_ba}\log^{\epsilon +1}n)$。存在$\epsilon > 0$，有$f(n)=\Omega(n^{\log_ba+\epsilon})$，且存在$c<1$和一个足够大的$n$，满足$af(\frac{n}{b})\leq cf(n)$，则$T(n)=\Theta(f(n))$。分治法分治法的基础是“划分-求解-合并”，其递归方程的格式为：$$ T(n)=aT(\frac{n}{b})+D(n)+C(n) $$其中字母的含义是：将问题分解为$a$个部分，$D(n)$是划分的耗时，$C(n)$是合并的复杂度。动态规划动态规划所适用的问题是，大问题的计算过程中，会重复计算很多子问题，造成不必要的开销。如果从子问题求解，并记住子问题的结果，就能够节省重复计算子问题的开销，其递归方程没有一个具体的通常格式，需要根据不同问题进行分析。贪心算法贪心算法的核心思想是，每一步的决策都做出当前的局部最优决策。这种算法的证明通常是通过归纳法以及交换论证法证明的。交换论证法通常是假定一个最优解，然后将所谓的最优决策换为贪心决策，最终得到更优的贪心解。后记具体的算法流程将在后续讲述。这门课我觉得最大的收获便是算法复杂度分析的数学工具。