暴力做法 1：
时间复杂度达不到要求
需要寻找两个数组的中位数，直接开一个大数组，把两个有序数组合并到大数组中，再找最中间那个数就是答案
暴力做法 2：
用两个指针指向两个有序数组的起始位置，逐个扫描元素，哪个指针所对应的值更小，就把哪个指针往后移动，移动到第 9 次的时候，到达中位数的位置
每次删除一个
第一个指针从 1 移动到 2，代表把 1 抛弃了，从 2 移动到 3，代表把 2 抛弃了，每移动一个指针，代表抛弃一个，最终找到目标值
找第 k 小数分析做法 1：
题目原来要求找两个有序数组的中位数，将问题转换成找两个有序数组合并之后第 k 小的数
每次删除 k / 2 个元素（比暴力方式删除的元素更多，效率更高），下一次删除前一个基础上剩余的 k / 2 个
下面模拟一下过程：
A 数组有 8 个元素，B 数组有 9 个元素，一共有 17 个元素，找它们合并之后第 9 小的数
第一轮，k = 9，k / 2 = 4，两个指针都指向第 4 个元素，比较这两个元素谁更小（选择小的部分删除），4 < 12，所以A 组中的这 k / 2 个元素肯定不包含第 k 小元素，直接把这 k / 2 个元素抛弃（一开始要找第 9 小数，由于已经把 4 个元素丢弃掉了，现在问题转换为找第 k - 4 个元素），然后移动指针，进行下一轮
第二轮，k = 5，k / 2 = 2，两个指针都指向第 2 个元素，比较这两个元素谁更小（选择小的部分删除），6 < 10，所以A 组中的这 k / 2 个元素肯定不包含第 k 小元素，直接把这 k / 2 个元素抛弃（一开始要找第 5 小数，由于已经把 2 个元素丢弃掉了，现在问题转换为找第 k - 4 - 2 个元素），然后移动指针，进行下一轮
第三轮，k = 3，k / 2 = 1，两个指针都指向第 1 个元素，比较这两个元素谁更小（选择小的部分删除），7 < 9，所以A 组中的这 k / 2 个元素肯定不包含第 k 小元素，直接把这 k / 2 个元素抛弃（一开始要找第 3 小数，由于已经把 1 个元素丢弃掉了，现在问题转换为找第 k - 4 - 2 - 1 个元素），然后移动指针，进行下一轮
第四轮，k = 2，k / 2 = 1，两个指针都指向第 1 个元素，比较这两个元素谁更小（选择小的部分删除），8 < 9，所以A 组中的这 k / 2 个元素肯定不包含第 k 小元素，直接把这 k / 2 个元素抛弃（一开始要找第 2 小数，由于已经把 1 个元素丢弃掉了，现在问题转换为找第 k - 4 - 2 - 1 - 1个元素），然后移动指针，进行下一轮
第五轮，k = 1，k / 2 = 0，找第 1 小的元素，A 数组的指针已经到尾，不能使用，那么我们就在 B 指针里面找第 1 小的元素，最终 9 就是第 k 小的元素
下面提出大部分题解都没有解释清楚的一些地方，真的让我很痛苦
下面详细分析一下疑问 2
要证明 A 数组中删除的这 k / 2 个元素一定是在中位数的左边
由于 A 数组是从小到大排序的，要保证这 k / 2 个数都在第 k 小数的左边，只需要保证最大的数 4 在第 k 小数的左边即可，也就是要证明最大的数 4 在第 k 小数的左边，也就是证明 4 右边的个数是否满足要求
保证最大的数 4 在第 k 小数的左边，4 右边的个数必须要大于等于 n - k(n - k 个数) + 1(第 k 个数）
首先两个数组都是有序的，4 右边的数大于 4，4 这个位置的数 < 12 这个位置的数，意味着12 右边的数都大于 12，肯定大于 4
要找 4 右边的个数：找比 4 大的数有多少个，看是否能填满，如果能填满甚至更多的话，就说明最大的数 4 一定是在第 k 小数的左边；如果比 4 大的数，不能填满右边的坑，就说明最大的数 4 不在第 k 小数的左边
A 数组、B数组中比 4 大的数是红框框起来的数：用总数 n 减去前面的数，红框框起来的数 n - (k / 2 * 2 - 1) 应该要大于等于右边的坑数 n - k + 1，才能够填满右边的坑
由于除法存在下取整，k 为奇数除以 2 向下取整，因此 / 2 * 2 要比原来的 k 要小 1
3 / 2 * 2，3 / 2 = 1，1 * 2 = 2
由于两种情况都成立，因此使用第 k 小数折半剔除的方法，可以证明每次剔除的数都在第 k 小数的左边的是成立的
概括
所谓的第 k 小 的数就是把两个有序的数组合并到一个大数组中，从左往右数第 k 个数就是答案，第一轮，k = 9，k / 2 = 4，两个指针都指向第 4 个元素，比较这两个元素谁更小（选择小的部分删除），4 < 12，所以A 组中的这 k / 2 个元素肯定不包含第 k 小元素，直接把这 k / 2 个元素抛弃（一开始要找第 9 小数，由于已经把 4 个元素丢弃掉了，现在问题转换为找第 k - 4 个元素），然后移动指针，进行下一轮
第一轮是从大数组的第 0 个位置开始数，第 9 个数就是我们的目标，第二轮 k 从 9 变成 5，也就是从大数组的 某个位置 开始数，第 5 个数就是我们的目标，虽然两轮数的个数不一样，但是最终的目标数都是同一个数，因为起点不一样
第二轮不再关心前面 4 个数字，只需要关心后面的这些数
相当于第一轮把所有的数字都填到坑里面，从左往右数，数到第 9 个就找到了，第二轮将红框框起来的那些数填到后面的坑里面，然后从左往右，数到第 5 个就是目标值
数据规模发生变化，剔除 4 个元素之后，数据规模从 n 变成 n - 4，每一轮都是从左往右数 k 个数，每一轮 k 的规模都一直减小
拓展找第 k 小的数删除的 4 个元素是位于合并数组当中的前 4 个元素吗？
答案是否定的
可以发现第一轮删除的元素并不是前 4 个元素 ( 1、3、5、7并不是连续的，而是跳跃的 )
但是一定是在目标值第 k 小的数的前面
给了 3 个有序数组，一共 25 个数，求第 13 小的数，按照求两个有序数组第 k 小数的方式，第一次就把第 13 小的数删掉了( 3 个数组合并后从小到大排序，第 13 小的数就是 13)
可以发现如果给了 3 个数组，直接套用原来的折半删除是行不通的
如果给 2 个有序数组就折半删除，也就是每次删除 k / 2 个元素，如果给 3 个有序数组，就每次删除 k / 3 个元素
时间复杂度要求 O( log(m + n) )
要证明要删除的这 k / 3 个数是在第 k 小数的左边
前面折半删除的例子证明的是比 4 大的数能不能填满这些坑
证明 4 左边比 4 小的数能够填多少个坑，如果比 4 小的数足够多，就有可能把 4 挤到 k 右边的位置，如果比 4 小的数没有这么多，4 就可以放在 k 前面的位置，或者更左边的位置
关心一下 4 加上比 4 小的个数总共有多少个，如果个数是小于 k 个，那么 4 一定是在第 k 小数的左边，如果个数是大于 k 个，就有可能把 4 挤到 k 右边的位置，就不满足要求了
现在比较 k / 3 = 4 的位置上比较 4、12、21，发现 4 最小，需要删除这 k / 3个数
现在确定 1、2、3 小于 4，4 右边的数大于 4，与 4 对应的另外两个指针上的数也都大于 4，因此它们后面的数也是大于 4 的，但是它们前面的数根据已知条件没有办法确定，假设这些不确定的数都是比 4 小的( 尽可能将比 4 小的数弄多一点，看是否足够多能够把 4 挤到 k 右边的位置 )
4 加上比 4 小的总个数就是 k / 3 * 3 - 2 个，我们希望它是小于 k 个，这样 4 才能在第 k 小数的左边
k / 3 * 3 有三种情况，注意下取整，第一种 k 恰好是 3 的倍数（ / 3 * 3 还是等于 k ），第二种 k 恰好是 3 的倍数多 1（ / 3 * 3 相当于减掉一个 1 ），第三种情况 k 恰好是 3 的倍数多 2（ / 3 * 3 相当于减掉一个 2 ），可以带入值去理解：k = 3、4、5
由此可以通过这 3 种情况证明 4 加上比 4 小的总个数是小于 k 个，4 在第 k 小数的左边，最终可以证明 删除的这 k / 3 个数是在第 k 小数的左边 这句话是成立的
下面来证明方案是否满足题目要求的时间复杂度，左边是折半删除：一开始假设个数是 n 个，每进行一次操作变成原规模的 1 / 2（每次删除 k / 2 个），进行 x 次操作后，最终规模缩减到 1，每次删除 k / 3 个的时间复杂度，每进行一次操作变成原规模的 2 / 3，进行 x 次操作后，最终规模缩减到 1，递归结束，两者的时间复杂度都是 O( log( m + n ) )
