寻找两个正序数组的中位数
1. 题目回顾
- 问题： 给定两个大小分别为 mm 和 nn 的正序数组 nums1 和 nums2，找出这两个正序数组的中位数。
- 约束： 算法的时间复杂度应该为 O(log(m+n))O(log(m+n)) 。
- 示例： [1,3] 和 [2] →→ 中位数为 2.0；[1,2] 和 [3,4] →→ 中位数为 2.5。
2. 核心思路：线性扫描与模拟归并
虽然这道题的最优解是二分查找，但这段代码采用了更朴素的 “模拟归并” 思路：
- 基本思想： 既然两个数组已经有序，那么它们合并后的整体也是有序的。我们不需要真的创建一个新数组来存储所有元素，只需要用两个指针分别指向两个数组的头部，每次比较两个指针所指的值，将较小的值“取出”，直到取到中位数所在的位置为止。
- 统一奇偶： 无论总长度是奇数还是偶数，中位数总是由中间的一个或两个数决定。通过计算 leftPos 和 rightPos，代码巧妙地用一个循环同时处理了这两种情况。
3. 算法详细步骤
3.1 递归终止条件（边界处理）
虽然本解法是迭代而非递归，但同样存在关键的边界判断逻辑，主要体现在 if 语句的判断顺序上：
- 越界检查优先： i < m && (j >= n || nums1[i] <= nums2[j])
- 首先检查 i < m，确保 nums1 还有元素。
- 接着检查 j >= n，如果 nums2 已经遍历完了，那么只能取 nums1 的元素。
- 最后才是数值比较 nums1[i] <= nums2[j]。这种短路求值机制防止了数组下标越界异常。
3.2 分解过程：双指针移动
- 初始化： 定义两个指针 i 和 j 分别指向 nums1 和 nums2 的起始位置。
- 确定目标位置：
- leftPos = (totalLen – 1) / 2：这是中位数左边的索引（对于奇数长度，它等于右边索引；对于偶数长度，它是中间偏左的那个）。
- rightPos = totalLen / 2：这是中位数右边的索引（对于奇数长度，它等于左边索引；对于偶数长度，它是中间偏右的那个）。
- 循环推进： 循环从 k=0 开始，一直走到 k == rightPos。每一步都代表我们在合并后的序列中找到了第 k+1 小的数。
3.3 解决过程：值的捕获
- 选取较小值： 在循环内部，比较 nums1[i] 和 nums2[j]，将较小的那个赋值给 rightVal，并将对应的指针后移。此时 rightVal 保存的是当前遍历到的最大值（即第 k 小的数）。
- 记录左侧中位数：
- 当循环变量 k 刚好等于 leftPos 时，说明当前的 rightVal 就是我们要找的中位数的左半部分（或者唯一部分）。
- 此时将 rightVal 备份到 leftVal 中。
3.4 合并过程：结果计算
- 循环结束： 当循环结束时，rightVal 必定停留在 rightPos 对应的值上。
- 公式计算： (leftVal + rightVal) / 2.0
- 若总长为奇数： leftPos == rightPos。在最后一次循环中，leftVal 被赋值为当前的 rightVal，随后循环结束，rightVal 没变。两者相加除以 2 等于其本身。
- 若总长为偶数： leftPos 比 rightPos 小 1。倒数第二次循环记录了 leftVal，最后一次循环更新了 rightVal。两者相加除以 2 即为平均值。
4. 代码实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int totalLen = m + n;
// 1. 确定我们需要遍历到的目标索引
// 例如长度为4，目标是索引1和2；长度为5，目标是索引2和2
int leftPos = (totalLen – 1) / 2;
int rightPos = totalLen / 2;
int i = 0, j = 0; // 双指针
int leftVal = 0, rightVal = 0; // 用于存储结果的两个关键值
// 2. 线性扫描，只需走到 rightPos 即可停止
for (int k = 0; k <= rightPos; k++) {
// 核心逻辑：谁小取谁，注意处理某个数组先遍历完的情况
if (i < m && (j >= n || nums1[i] <= nums2[j])) {
rightVal = nums1[i++];
} else {
rightVal = nums2[j++];
}
// 3. 如果当前步数到达了左中位数的位置，记录下来
if (k == leftPos) {
leftVal = rightVal;
}
}
// 4. 利用数学特性统一返回结果
// 奇数时 leftVal == rightVal，偶数时取平均
return (leftVal + rightVal) / 2.0;
}
}
5. 复杂度分析
这是该解法最大的短板，也是面试中需要注意的点。
- 时间复杂度： O(m+n)
- 在最坏情况下（例如一个数组的所有元素都小于另一个数组），我们需要遍历大约 (m+n)/2 次。
- 这属于线性时间复杂度。虽然对于小规模数据很快，但对于大规模数据，它不满足题目要求的 O(log(m+n))) （对数级）。
- 空间复杂度： O(1)
- 只使用了 i, j, k, leftVal, rightVal 等几个变量，没有开辟额外的数组空间，空间效率非常高。
只出现一次的数字
1. 题目回顾
- 问题描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
- 约束条件： 你的算法应该具有线性时间复杂度 O(n)O(n) 。你能不使用额外空间来实现吗？
- 示例：
- 输入：[2, 2, 1] →→ 输出：1
- 输入：[4, 1, 2, 1, 2] →→ 输出：4
2. 核心思路：位运算与异或性质
虽然题目可以归类为“查找”类问题，但最优雅的解法并非传统的排序或哈希表，而是利用位运算（Bit Manipulation）中的异或（XOR）操作。这其实是一种数学层面的“线性扫描”。
-
异或运算的三大特性：
- 归零律： 任何数与自身异或等于 0 ( a⊕a=0a⊕a=0 )。
- 恒等律： 任何数与 0 异或等于其本身 ( a⊕0=aa⊕0=a )。
- 交换律与结合律： 运算顺序不影响结果 ( a⊕b⊕a=(a⊕a)⊕b=0⊕b=ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b )。
-
解题策略： 将数组中所有数字进行累积异或。成对出现的数字会互相抵消变成 0，最终剩下的结果就是那个唯一的数字。
3. 算法详细步骤
3.1 递归终止条件（边界处理）
虽然最优解通常使用迭代（循环），但如果从逻辑完整性角度考虑边界：
- 单元素数组： 如果数组长度仅为 1，无需计算，直接返回该元素。
- 初始状态： 我们需要一个“累加器”变量，初始值必须设为 0。因为 0 是异或运算的单位元，不会改变第一个参与运算的数字的值。
3.2 分解过程：线性扫描
我们将问题分解为 NN 个简单的子步骤，即遍历数组中的每一个元素。
- 指针移动： 设置一个循环变量 i 从 0 遍历到 nums.length – 1。
- 数据流： 在每一步中，我们取出当前元素 nums[i]，将其视为待处理的“新信息”。
3.3 解决过程：值的捕获（异或消除）
这是算法的核心执行阶段。我们不需要额外的存储空间来记录谁出现过，而是通过位运算实时“消除”重复项。
- 操作： 执行 result = result ^ nums[i]。
- 动态演示：
- 假设数组为 [4, 1, 2, 1, 2]。
- 遇到 4：结果变为 4。
- 遇到 1：结果变为 4^1。
- 遇到 2：结果变为 4^1^2。
- 遇到 1：结果变为 4^(1^1)^2 →→ 4^0^2 →→ 4^2。（此时第一个 1 被成功消除）。
- 遇到 2：结果变为 4^(2^2) →→ 4^0 →→ 4。（此时 2 也被消除）。
3.4 合并过程：结果计算
- 最终态： 当循环结束时，所有的“对子”都已经变成了 0。
- 输出： 累加器中保留的唯一非零数值即为答案。由于异或运算的特性，这个结果天然就是我们要找的“单身”数字，无需再进行额外的比较或筛选。
4. 代码实现
class Solution {
public int singleNumber(int[] nums) {
// 初始化结果为0，作为异或的起始基准
int result = 0;
// 线性扫描整个数组
for (int num : nums) {
// 核心操作：异或运算
// 相同的数字会抵消为0，不同的数字会保留
result ^= num;
}
// 返回最终剩下的数字
return result;
}
}
5. 复杂度分析
- 时间复杂度： O(n)
- 我们只需要遍历数组一次，其中 n 是数组的长度。每个元素的异或操作是常数时间 O(1) 的。
- 空间复杂度： O(1)
- 这是一个原地算法。我们只使用了一个额外的变量 result 来存储中间状态，没有使用哈希表或辅助数组，完全符合题目“不使用额外空间”的要求。
