day13题目：88. 合并两个有序数组、31. 下一个排列、4. 寻找两个正序数组的中位数
学习计划链接：冲刺春招-精选笔面试 66 题大通关
今日知识点：数组、双指针、二分，难度为简单、中等、困难
昨日题目链接：冲刺春招-精选笔面试 66 题大通关 day12
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 **到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]
解释： 需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]
解释： 需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入： nums1 = [0], m = 0, nums2 = [1], n = 1
输出： [1]
解释： 需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
-109 <= nums1[i], nums2[j] <= 109
进阶： 你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
思路
显而易见的双指针
设 i、j 分别指向nums1、nums2最后一个元素，k指向合并后下标
let [i, j, k] = [m-1, n-1, m+n-1];
比较 nums1[i] 和 nums2[j]，谁大就将谁放至 nums1[k] 将其对应 i 或 j 前移
while(i >= 0 && j >= 0) {
if(nums1[i] >= nums2[j]) {
nums1[k--] = nums1[i];
--i;
} else {
nums1[k--] = nums2[j];
--j;
}
}
需注意的是当一轮循环结束后仍有 j >= 0 说明 nums2 中仍有元素未被合并，这个时候直接将其放入 nums1 即可
while(j >= 0) {
nums1[k--] = nums2[j];
--j;
}
代码
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number}
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
let [i, j, k] = [m-1, n-1, m+n-1];
while(i >= 0 && j >= 0) {
if(nums1[i] >= nums2[j]) {
nums1[k--] = nums1[i];
--i;
} else {
nums1[k--] = nums2[j];
--j;
}
}
while(j >= 0) {
nums1[k--] = nums2[j];
--j;
}
return nums1;
};
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入： nums = [1,2,3]
输出： [1,3,2]
示例 2：
输入： nums = [3,2,1]
输出： [1,2,3]
示例 3：
输入： nums = [1,1,5]
输出： [1,5,1]
提示：
思路
不讲武德版：调algorithm库里的全排列函数捏
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(), nums.end());
}
};
首先，下一个排列总是比当前排列要 大，除非该排列已经是最大的排列。所以我们需要找到一个 大于当前序列 的新序列，且 变大的幅度 尽可能 小。具体地有：
将一个左边的 较小数 与一个右边的 较大数 交换，以能够让当前排列变大，从而得到下一个排列
同时这个 较小数 需要尽量 靠右，而 较大数 需要尽可能 小
交换完成后，较大数右边的数 需要 按照升序重新排列吗，这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。 具体地，我们这样描述该算法，对于长度为 n 的排列 a：
首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样 较小数 即为 a[i]。此时 [i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中 从后向前 查找第一个元素 j ，满足 a[i] < a[j]。这样 较大数 即为 a[j]。
交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为 降序。
接使用 双指针 反转区间 [i+1,n) 使其 变为升序。
代码
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
let len = nums.length;
let i = len-2;
while(i >= 0 && nums[i] >= nums[i+1]) --i;
if(i >= 0) {
let j = len-1;
while(j >= 0 && nums[i] >= nums[j]) --j;
[nums[i], nums[j]] = [nums[j], nums[i]]; // 交换
}
var reverseList = function(nums, s, e) {
if(s >= e) return nums;
while(s <= e) {
[nums[s], nums[e]] = [nums[e], nums[s]];
++s,--e;
}
return nums;
}
return reverseList(nums, i+1, len-1);
};
给定两个大小分别为 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
提示：
-106 <= nums1[i], nums2[i] <= 106
思路
let len = m+n;
if(len%2 == 0) {
return (nums1[len/2]+nums1[(len/2)-1])/2;
} else return nums1[(len-1)/2];
代码
思路一
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let [m, n] = [nums1.length, nums2.length];
nums1 = nums1.concat(new Array(n).fill(0));
let [i, j, k] = [m-1, n-1, m+n-1];
while(i >= 0 && j >= 0) {
if(nums1[i] >= nums2[j]) {
nums1[k--] = nums1[i];
--i;
} else {
nums1[k--] = nums2[j];
--j;
}
}
while(j >= 0) {
nums1[k--] = nums2[j];
--j;
}
let len = m+n;
if(len%2 == 0) {
return (nums1[len/2]+nums1[(len/2)-1])/2;
} else return nums1[(len-1)/2];
};
