4. 寻找两个正序数组的中位数

题目链接

4. 寻找两个正序数组的中位数

标签

数组 二分查找 分治

思路

本题是 十分困难 的，如果比较忙，可以跳过本题。

本题难点在于如何保证时间复杂度为 $O(\log n)$，显然要使用 二分法，不过应该如何使用 二分法 呢？对于有奇数个 (偶数的情况与之类似，不过需要找两个中位数，求平均值) 元素的合并后的升序数组，可以这样想：求中位数就是求中间元素，即求合并后的数组中第 k = (nums1.length + nums2.length) / 2 + 1 个数，那么可以分别在两个数组中取 k / 2 个数，根据情况进行讨论：

• 如果 nums1[k / 2] < nums1[k / 2]，又因为 nums1 是升序的，所以 nums1 的区间 $[0,\frac{k}{2}]$ 之内的所有元素都只能是 前 k 个数，这个区间中不存在 第k个数，舍弃这个区间；
• 如果 nums1[k / 2] > nums1[k / 2]，又因为 nums2 是升序的，所以 nums2 的区间 $[0,\frac{k}{2}]$ 之内的所有元素都只能是 前 k 个数，这个区间中不存在 第k个数，舍弃这个区间；
• 如果 nums1[k / 2] == nums2[k / 2]，则可以任意将这种情况合并到第一种情况和第二种情况中。

如果能理解这一点，则走出了第一步，剩下的步骤与第一步类似，这里就不做赘述了，请看下面这张图，其中描述了如何寻找“合并后”的数组中的左中位数：

看完这张图之后肯定会觉得莫名其妙，可以直接看代码，其中有一个 获取 “合并后”的升序数组中 的第 k 个元素 的方法，这张图就是用于描述这个方法的 常规流程 的。至于 idx1 或 idx2 到边界的情况，请看下面这张图：

代码

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.length, len2 = nums2.length;int totalLen = len1 + len2;if (totalLen % 2 == 1) { // 如果 两个数组合并的数组的长度 为奇数int midIndex = totalLen / 2; // 获取 中间元素 的索引double median = getKthEle(nums1, nums2, midIndex + 1);return median;} else { // 如果 两个数组合并的数组的长度 为偶数int midLIndex = totalLen / 2 - 1, // 获取 中间偏左的元素 的索引midRIndex = totalLen / 2; // 获取 中间偏右的元素 的索引double median = (getKthEle(nums1, nums2, midLIndex + 1)+ getKthEle(nums1, nums2, midRIndex + 1)) / 2.0; // 求两个中间元素的平均值return median;}}// 获取 “合并后”的升序数组中 的第 k 个元素private int getKthEle(int[] nums1, int[] nums2, int k) {int len1 = nums1.length, len2 = nums2.length;int idx1 = 0, idx2 = 0; // idx1, idx2 分别为 nums1, nums2 的索引while (true) {if (idx1 == len1) { // 如果 idx1 到边界了，说明 nums1 中的元素全被舍弃了return nums2[idx2 + k - 1]; // 则返回 nums2 中的元素}if (idx2 == len2) { // 如果 idx2 到边界了，说明 nums2 中的元素全被舍弃了return nums1[idx1 + k - 1]; // 则返回 nums1 中的元素}if (k == 1) { // 如果 k == 1 了，则此时返回 nums1[idx1] 和 nums2[idx2] 中的较小值作为结果return Math.min(nums1[idx1], nums2[idx2]);}int half = k >> 1; // 获取 k 除以 2 的结果int newIdx1 = Math.min(idx1 + half, len1) - 1; // 获取新的 idx1，并防止越界int newIdx2 = Math.min(idx2 + half, len2) - 1; // 获取新的 idx2，并防止越界int discard; // 被舍弃的元素个素if (nums1[newIdx1] <= nums2[newIdx2]) { // 如果 nums1 中指定索引的元素 <= nums2 中指定索引的元素discard = newIdx1 - idx1 + 1; // 舍弃的元素个数为 索引之差 + 1idx1 = newIdx1 + 1; // 舍弃 nums1 的区间 [idx1, newIdx1] 内的元素} else { // 否则 nums1 中指定索引的元素 > nums2 中指定索引的元素discard = newIdx2 - idx2 + 1; // 舍弃的元素个数为 索引之差 + 1idx2 = newIdx2 + 1; // 舍弃 nums2 的区间 [idx2, newIdx2] 内的元素}k -= discard; // 舍弃元素}}
}

92. 反转链表 II

题目链接

92. 反转链表 II

标签

链表

思路

反转部分链表

如上图，反转链表就是上面的这些操作。

寻找 prev

不过在进行如上操作之前先要获取 prev，其实不难，只需要让 prev 从 哨兵节点sentinel 开始移动 left - 1 次。例如上图，left = 2，所以 prev 从 sentinel 开始移动 2 - 1 = 1 次即可。

为什么使用 sentinel

如果没有写过链表类似的题目，一上来就看到 哨兵节点sentinel 可能会有些懵，实际上 sentinel 是为了处理 left = 1 的情况而存在的。在 left = 1 的情况下，prev 就没有办法指向一个具体的节点，这时如果给链表添加一个 哨兵节点sentinel，那么 prev 可以指向 sentinel，从而保证反转操作能够正确执行。

代码

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode sentinel = new ListNode(0, head); // 使用哨兵节点可以处理 left == 1 的情况ListNode prev = sentinel;// 让 prev 移动 left - 1 次，移动到第 left 个节点的前一个节点处for (int i = 0; i < left - 1; i++) {prev = prev.next;}ListNode oldHead = prev.next; // 待反转 的部分链表的头部for (int i = left; i < right; i++) { // 反转 right - left 次ListNode next = oldHead.next; // 获取 oldHead 的下一个节点 nextoldHead.next = next.next; // oldHead 指向 next 的下一个节点next.next = prev.next; // next 指向 oldHeadprev.next = next; // prev 指向 next}return sentinel.next; // 返回哨兵节点指向的链表}
}

155. 最小栈

题目链接

155. 最小栈

标签

栈 设计

思路

栈的实现

栈这种数据结构不难实现，使用链表即可实现，本题可以通过实现一个栈来解决。

栈是 特殊的链表，特殊之点在于它不需要访问链表中的其他元素，只需要访问链表的尾节点。可以采用 倒序链表 的方式来实现栈，记录栈顶元素 top (即 链表的尾节点) 即可。对于添加新节点，有以下两种情况：

• 如果栈顶元素 top 为 null，则将 新节点 放到栈顶元素 top 的位置。
• 如果栈顶元素 top 不为 null，则让新元素指向原先的栈顶元素，然后让栈顶指针指向新元素。

下图演示了上述的添加过程：

最小值的实现

本题还要求能够返回栈中的最小值，这并不难实现。如果没有限制时间复杂度为常数级的话，可以遍历链表，来找最小值。不过本题限制了常数级的时间复杂度，这里就需要使用 空间换时间 的思想：将节点压入栈后的最小值存储到当前节点中。这样一来，要获取栈中的最小值，只需要获取栈顶元素的 最小值属性 即可。

代码

class MinStack {// 放到栈里面的节点的数据类，存储 当前元素的值 和 当前栈中的最小元素，此外还有指向下一个节点的指针private static class Node {int val;int min;Node next;Node(int val, int min) {this.val = val;this.min = min;}}private Node top; // 保存链表的尾节点，即记录栈顶元素public MinStack() {}public void push(int val) {if (top == null) { // 如果 栈顶 为空// 则 当前元素 就是 栈中的最小值top = new Node(val, val); // 将 当前元素 作为 栈顶元素} else { // 如果 栈顶 不为空// 则选取 栈顶元素的最小值 和 当前元素 中的较小值作为 加入当前元素后的 栈中的 最小值int min = Math.min(top.min, val);Node newTop = new Node(val, min);newTop.next = top; // 让 新的栈顶元素 指向 原来的栈顶元素top = newTop; // 将 当前元素 作为 新的栈顶元素}}public void pop() {if (top == null) { // 如果 栈顶 为空return; // 则不进行操作，最好报错，这里就直接返回了}top = top.next; // 将 栈顶元素 弹出栈}public int top() {return top.val; // 返回 栈顶元素 的值}public int getMin() {return top.min; // 返回 栈顶元素 的最小值}
}