每日两道力扣，day4
每日两道力扣，day4
每日两道力扣，day4
每日两道力扣，今日是：
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
第一题：搜索二维矩阵
1.思路：
基于咱们前三天的努力，想必各位大佬也大致摸清了二分查找的应用场景。这个题依旧是搜素 + 有序数组，所以咱们直接掏一手二分查找拿下他。可是这个题有点硬，咱们得细细分析，才能做到万无一失。
（1）方法一：既然咱们已经知道需要运用二分查找，面对这个二维数组，而且数据要求并不是那么的苛刻，咱们其实可以考虑运用for循环，一行一行进行二分查找（或一列一列，因为小编功力有限，咱们这里采用一行一行进行二分查找）。因为这个二维数组的高是m，宽是n。所以按照这个思路进行二分查找的时间复杂度是O（mlogn)。依旧超过了100.00%的人。
（2）方法二：但你要是问我有没有更快的方法。我的回答是：“有的有的，兄弟”，在方法一中咱们执行了m次二分查找。可是咱们大可以用一次二分查找就秒掉这个题。降维打击 —— 当成一个一维数组来二分，仔细看题目的两个条件：
- 每行从左到右递增。
- 每行的第一个整数大于前一行的最后一个整数。
这两个条件连在一起说明什么？说明如果你把这个矩阵像贪吃蛇一样拉直，它完完全全就是一个完美的升序一维数组！既然它本质是个一维有序数组，我们为什么不直接对“整个矩阵”做一次二分查找呢？
核心魔法：一维下标转二维坐标
假设矩阵是 M M M 行 N N N 列。一维数组的下标 idx，怎么还原成二维矩阵里的行 row 和列 col 呢？
- 行号
row=idx / n（除了列数，就知道在第几行） - 列号
col=idx % n（对列数取余，就知道在该行的第几列）
注：row是高，column是宽。
2.代码实现：
（1）方法一：
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(),n = matrix[0].size(); bool res = false; for(int i = 0; i < m;i++) { int left = 0, right = n-1; while(left <= right) { int mid = left + (right - left)/2; if(matrix[i][mid] > target) { right = mid - 1; } else if(matrix[i][mid] < target) { left = mid + 1; } else { res = true; break; } } if(res == true) break; } return res; } }; （2）方法一：（优化版）
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); for(int i = 0; i < m; i++) { int left = 0, right = n - 1; while(left <= right) { int mid = left + (right - left) / 2; if(matrix[i][mid] > target) { right = mid - 1; } else if(matrix[i][mid] < target) { left = mid + 1; } else { // 修复：找到了直接返回 true，结束战斗！ return true; } } } // 如果所有的行都找完了还没 return true，说明真的没有 return false; } }; （3）方法二：
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size(); // 虚拟的一维数组的首尾指针 int left = 0; int right = m * n - 1; while(left <= right) { int mid = left + (right - left) / 2; // 魔法：把一维的 mid 还原成二维的行列坐标 int row = mid / n; int col = mid % n; int mid_val = matrix[row][col]; // 下面就是最最普通的标准二分查找了！ if(mid_val == target) { return true; } else if(mid_val < target) { left = mid + 1; } else { right = mid - 1; } } return false; } }; 3.细节
如果我是力扣出题人，我为了恶心人。我会毫不犹豫得扩大 m ,n。使得方法一运行超时。由此这个题就变成了hard题。不会方法二的人，看到了这个题就只能干瞪眼，在心里咒骂出题的臭老头（小编今年刚好18，正值青春大好年华，可不是臭老头，顶多是个死宅男）
可惜了，可惜我不是。
第二题：寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
1.思路
hard题…作为一个力扣才写了80多道的初学者，小编也只能尝试一下。讲一下小编遇见这个题的第一思路：我想创建一个大小为（m+n)的数组nums3用来合并nums1,nums2，然后直接在nums3内部直接二分查找就ok了，可事实真的如此嘛？我这种方法的时间复杂度是O(m+n)，不符合题目要求.
难道普通人真的就写不出hard题了吗？我不信，然后我尝试了半小时。没有任何思绪，还是功夫不够深。我暂时认了。
于是，我求助了gemini，它提出了一种我从所未见的方法。
寻找“完美切割线”。
（1）我们不需要真的合并数组。中位数的本质是什么？中位数就是一条“切割线”，它把所有数字分成了长度相等的左右两半，并且左半边的所有数字都小于右半边的所有数字。
假设我们在 nums1 的第 i i i 个位置切一刀，在 nums2 的第 j j j 个位置切一刀。
切割线左边共有 i + j i + j i+j 个元素，右边也有这么多元素。
为了让左右两半元素个数相等（或左边多 1 个），必须满足：
i + j = m + n + 1 2 i + j = \frac{m + n + 1}{2} i+j=2m+n+1
既然 j j j 可以通过 i i i 算出来，我们只需要在较短的那个数组（假设是 nums1）中，对切割线的位置 i i i 进行二分查找就行了！
（2）什么样的切割线是“完美的”？
切割线左边的最大值，必须小于等于右边的最小值。也就是产生交叉对比：
nums1切割线左边元素 ≤ \le ≤nums2切割线右边元素nums2切割线左边元素 ≤ \le ≤nums1切割线右边元素
即切完之后，切口附近有 4 个关键数字：
nums1切口左边的最大值：nums1LeftMaxnums1切口右边的最小值：nums1RightMinnums2切口左边的最大值：nums2LeftMaxnums2切口右边的最小值：nums2RightMin
因为数组本身就是有序的，所以 nums1LeftMax 肯定 ≤ \le ≤nums1RightMin。
要想满足“总左半边 ≤ \le ≤ 总右半边”，我们只需要交叉对比：
- 必须满足：
nums1LeftMax <= nums2RightMin - 必须满足：
nums2LeftMax <= nums1RightMin
只要这两个交叉条件同时成立，恭喜你，这“一刀切”就是完美的！(对应代码里的 if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin))
（3）用二分查找来“挪动”这把刀
既然 j j j 是由 i i i 决定的，那问题就变得极其简单了：我们只需要在 nums1 这个数组里，寻找正确的切割点 i i i。
怎么找 i i i 最快？用二分查找！
初始状态：left = 0, right = m。每次试一个中点 i = left + (right - left) / 2。
试了一刀后，看看交叉对比的结果：
- 完美命中：交叉条件都满足。直接算中位数！（奇数就取左边两个的最大值，偶数就取左边最大和右边最小的平均值）。
nums1LeftMax > nums2RightMin：这说明nums1左边的数字太大了。既然大了，说明我们在nums1里切得太靠右了，划进来了太多大数字。动作：刀往左挪，right = i - 1;。- 否则（
nums2LeftMax > nums1RightMin）：这说明我们在nums2左边的数字太大了。因为 j j j 和 i i i 是此消彼长的，nums2左边太大，说明 j j j 太大，也就说明我们在nums1里切得太靠左了， i i i 给得太少了。动作：刀往右挪，left = i + 1;。
(最后，代码里那几个 INT_MIN 和 INT_MAX 是干嘛的？如果一刀切在了数组最边缘，左边没数字了，就当它是极小值 − ∞ -\infty −∞；右边没数字了，就当它是极大值 + ∞ +\infty +∞。这样就不妨碍我们进行交叉对比，也不会发生越界报错。)
2.代码实现：
#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(); // 分割线左边应该有的总元素个数 int totalLeft = (m + n + 1)/2; // 在 nums1 的区间 [0, m] 里二分查找切割线位置 i int left = 0, right = m; while(left <= right) { // nums1 的切割点 int i = left + (right - left)/2; // nums2 的切割点（由 i 推导出来） int j = totalLeft - i; // 获取切割线左右两侧的 4 个元素 // 如果切割线在最边缘，为了不越界，赋予极值（INT_MIN 或 INT_MAX） int nums1LeftMax = (i==0) ? INT_MIN : nums1[i-1]; int nums1RightMin = (i==m) ? INT_MAX : nums1[i]; int nums2LeftMax = (j==0) ? INT_MIN : nums2[j-1]; int nums2RightMin = (j==n) ? INT_MAX : nums2[j]; // 灵魂拷问：这条切割线完美吗？ if(nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) { // 完美！已经找到了正确的切割线 // 如果总长度是奇数，中位数就是左半边最大的那个元素 if((m + n) % 2 == 1) { //这里编译器帮我做了隐式类型转换，将int优化为double return max(nums1LeftMax,nums2LeftMax); } // 如果总长度是偶数，中位数是 (左半边最大 + 右半边最小) / 2.0 else { return (max(nums1LeftMax,nums2LeftMax) + min(nums1RightMin,nums2RightMin)) / 2.0; } } // 如果 nums1 左边的元素太大了，说明 nums1 的切割线划得太靠右了，往左逼近 else if(nums1LeftMax > nums2RightMin) { right = i - 1; } // 否则说明 nums1 的切割线划得太靠左了，往右逼近 else { left = i + 1; } } // 语法需要，正常情况一定会在 while 里 return return 0.0; } }; 3.细节
（1）我们必须保证nums1是一个短数组，不然数组会越界。
（2）关于切割点i可能的疑惑
（3）最后面我们一定要return 0.0;作为占位返回，来哄骗编译器，不然编译器这个认死理的家伙，跑到一半就给咱们这个完美的程序停了。
好了，今天的每日两道力扣到这里就算是结束了，看完是不是感觉有所收获呢？如果学有所获的话，麻烦给个三连支持一下呗。感谢观看，您的支持，将是我前进路上的重要动力。
