废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【数组组合】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
合并两个有序数组【EAZY】
其实这道题的思路和合并两个有序链表大同小异
题干
直接粘题干和用例
解题思路
给出解题思路，最好有图
- step 1：使用三个指针，i指向数组A的最大元素，j指向数组B的最大元素，index指向数组A空间的结尾处。
- step 2：从两个数组最大的元素开始遍历，直到某一个结束，每次取出较大的一个值放入数组A空间的最后，然后指针一次往前。
- step 3：如果数组B先遍历结束，数组A前半部分已经存在了，不用管；但是如果数组A先遍历结束，则需要把数组B剩余的前半部分依次逆序加入数组A前半部分，类似归并排序最后的步骤。
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：迭代
技巧：双指针（逆序双指针）
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { public void merge(int A[], int m, int B[], int n) { // 1 入参校验，数组长度需要满足条件 if (A == null || A.length < m + n) { return; } // 2 因为A数组后几位是空着的，为了不让前面元素的移动引起的挪动导致整个A发生元素移动，问题可以转换为找最大值，先把最大值放到最后的空位置 int maxIndex = m + n - 1; int i = m - 1; int j = n - 1; // 双指针从大到小移动,比较A和B的元素将较大的放到A中后边的位置 while (i >= 0 && j >= 0) { A[maxIndex--] = A[i] > B[j] ? A[i--] : B[j--]; } // 如果B还有剩余合并到A中；如果是A有剩余，无需合并到A中 while (j >= 0) { A[maxIndex--] = B[j--]; } } }
复杂度分析
- 时间复杂度：O(m+n)。 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
- 空间复杂度：O(m+n)。 需要建立长度为 m+n 的中间数组
