大家好，我是苍何。
最近，小米也陆续开奖了，但薪资方面，稍微有些保守。
硕士 211，只给 15 K，小伙看笑了，然后直接拒绝。
但是一看是武汉，那其实已经不算差了，要知道第一武汉大学生多的吓人，硕士 211，在武汉并不是什么顶级的存在，其次武汉工资一向出了名的低，能开到 15 k 不算差了。
别问我怎么知道的，我塔喵在武汉找了半圈工作，也很难开到我满意的数字，大部分软件开发岗的薪资都很低，除去大厂能给的多些，但也是少的可怜，像是挤牙膏，挤一挤，其实也没多少。
刚一毕业，不建议直接待武汉这种二线城市，去一线历练个几年，把工资基准抬高，回来即使打折，折后还能勉强活一活。
不过你别说，小米现在招人水准是越来越高了，据说，双非很难再入其法眼，校招如此，社招也如此，人才旺盛的后果是，企业有了更多的选择，对企业来说，学历好就是能力好，学历大于一切。
那学历不好的有什么办法呢？有？去掉大厂梦，选择细分增长赛道，选择独角兽企业或者细分增长赛道中小企业。
AI、新能源（不要去锂电池电芯厂，去增量方向，如储能赛道）、半导体芯片。。。
最后，告诉大家个消息，苍何也终于要再次做回牛马了，明天，我将再次，背起我那参加活动送的双肩包，在上班的人流中，渐行渐远。
好啦，关于小米开奖这薪资，你有什么看法呢？欢迎评论区讨论。
...
回归主题。
今天来一道小米开发考过的一道面试算法题，给枯燥的牛马生活加加油😂。
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，请你找出并返回这两个正序数组的 中位数。
要求算法的时间复杂度为 O(log (m+n))。
示例
示例 1:
输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释: 合并数组 = [1,2,3] ，中位数 2
示例 2:
输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.50000
解释: 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
解题思路
由于题目要求时间复杂度为 O(log(m+n))，我们不能简单地合并数组再查找中位数，而是需要用 二分查找 来找到两个数组的中位数。
解法的核心思想是：
二分查找分割点：我们将
nums1和nums2分割成两个部分，使得左边部分的元素个数与右边部分相同或相差 1。保持左右部分的元素大小关系：需要保证左边部分的最大值小于等于右边部分的最小值。
中位数的计算：
如果总长度为奇数，中位数是左边部分的最大值。
如果总长度为偶数，中位数是左边部分最大值与右边部分最小值的平均值。
代码实现
以下是基于上述思路的代码实现：
Java 代码
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 确保 nums1 是较短的数组，以减少二分查找的复杂度
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
// totalLeft 是左半部分的总元素数
int totalLeft = (m + n + 1) / 2;
int left = 0, right = m;
while (left < right) {
// i 是 nums1 的分割点
int i = (left + right + 1) / 2;
// j 是 nums2 的分割点，使得左半部分有 totalLeft 个元素
int j = totalLeft - i;
// 检查分割是否合适，若 nums1[i-1] > nums2[j]，则需要缩小 i 的范围
if (nums1[i - 1] > nums2[j]) {
right = i - 1;
} else {
left = i;
}
}
// 最终确定的分割点 i 和 j
int i = left;
int j = totalLeft - i;
// 处理边界条件，若 i 或 j 位于数组边界，则使用最小值或最大值
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
// 如果总长度是奇数，返回左边部分的最大值
if ((m + n) % 2 == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
// 如果总长度是偶数，返回左边最大值与右边最小值的平均值
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
}
}
}
C++ 代码
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 确保 nums1 是较短的数组
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
// totalLeft 表示左半部分的总元素个数
int totalLeft = (m + n + 1) / 2;
int left = 0, right = m;
while (left < right) {
int i = (left + right + 1) / 2;
int j = totalLeft - i;
// 如果 nums1[i-1] > nums2[j]，说明 i 太大了，需要向左移动
if (nums1[i - 1] > nums2[j]) {
right = i - 1;
} else {
// 否则 i 太小了，需要向右移动
left = i;
}
}
// 最终的分割点 i 和 j
int i = left;
int j = totalLeft - i;
// 左半部分最大值
int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];
int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];
// 右半部分最小值
int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
int nums2RightMin = (j == n) ? INT_MAX : nums2[j];
// 如果总长度是奇数，返回左半部分最大值
if ((m + n) % 2 == 1) {
return max(nums1LeftMax, nums2LeftMax);
} else {
// 如果总长度是偶数，返回左半部分最大值和右半部分最小值的平均值
return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2.0;
}
}
};
Python 代码
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
# 确保 nums1 是较短的数组，以优化二分查找的效率
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
# 左半部分的元素个数
total_left = (m + n + 1) // 2
left, right = 0, m
while left < right:
i = (left + right + 1) // 2
j = total_left - i
# 如果 nums1[i-1] > nums2[j]，说明 i 太大了，需左移
if nums1[i - 1] > nums2[j]:
right = i - 1
else:
# 否则 i 太小，右移
left = i
# 确定最终的分割点 i 和 j
i = left
j = total_left - i
# 边界条件处理，获取左半部分最大值
nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
# 获取右半部分最小值
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_right_min = float('inf') if j == n else nums2[j]
# 如果总长度是奇数，中位数是左半部分最大值
if (m + n) % 2 == 1:
return max(nums1_left_max, nums2_left_max)
else:
# 如果总长度是偶数，中位数是左半部分最大值与右半部分最小值的平均
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0
复杂度分析
时间复杂度：
O(log(min(m, n)))，因为我们对较小的数组进行二分查找。空间复杂度：
O(1)，只使用了常数空间。
ending
你好呀，我是苍何。是一个每天都在给自家仙人掌讲哲学的执着青年，我活在世上，无非想要明白些道理，遇见些有趣的事。倘能如我所愿，我的一生就算成功。共勉 💪
点击关注下方账号，你将感受到一个朋克的灵魂，且每篇文章都有惊喜。
感谢大家一直以来的阅读、在看和转发，我会把流量主收益都用来发红包，大家可在公众号页面发送相关暗号关键词获取抽奖，每一篇文章会给到一个不同的暗号，对应的抽奖都是独立的，此篇暗号为【看笑了】，在后台回复【看笑了】，即可点击进去参与抽奖！抽奖内容、金额、个数等都无变化，在开奖前参与抽奖，操作均有效。
注意，后台（不是评论区，是后台）回复【看笑了】即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
就像大家之前回复【八股】一样。
