目录
4. 寻找两个正序数组的中位数
题目链接
标签
数组 二分查找 分治
思路
本题是 十分困难 的，如果比较忙，可以跳过本题。
本题难点在于如何保证时间复杂度为 O ( log n ) O(\log n) O(logn)，显然要使用 二分法，不过应该如何使用 二分法 呢？对于有奇数个 (偶数的情况与之类似，不过需要找两个中位数，求平均值) 元素的合并后的升序数组，可以这样想：求中位数就是求中间元素，即求合并后的数组中第 k = (nums1.length + nums2.length) / 2 + 1 个数，那么可以分别在两个数组中取 k / 2 个数，根据情况进行讨论：
- 如果
nums1[k / 2] < nums1[k / 2]，又因为nums1是升序的，所以nums1的区间 [ 0 , k 2 ] [0, \frac{k}{2}] [0,2k] 之内的所有元素都只能是 前k个数，这个区间中不存在 第k个数，舍弃这个区间； - 如果
nums1[k / 2] > nums1[k / 2]，又因为nums2是升序的，所以nums2的区间 [ 0 , k 2 ] [0, \frac{k}{2}] [0,2k] 之内的所有元素都只能是 前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; // 舍弃的元素个数为 索引之差 + 1
idx1 = newIdx1 + 1; // 舍弃 nums1 的区间 [idx1, newIdx1] 内的元素
} else { // 否则 nums1 中指定索引的元素 > nums2 中指定索引的元素
discard = newIdx2 - idx2 + 1; // 舍弃的元素个数为 索引之差 + 1
idx2 = newIdx2 + 1; // 舍弃 nums2 的区间 [idx2, newIdx2] 内的元素
}
k -= discard; // 舍弃元素
}
}
}
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 的下一个节点 next
oldHead.next = next.next; // oldHead 指向 next 的下一个节点
next.next = prev.next; // next 指向 oldHead
prev.next = next; // prev 指向 next
}
return sentinel.next; // 返回哨兵节点指向的链表
}
}
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; // 返回 栈顶元素 的最小值
}
}
