2080324 今日算法

把两个有序数组接起来，然后用快排的分区函数的找中位数？楼下继续…

这是 leetcode 的题目吗，好像见过。有序数组归并排序。总数除以二得到中位数。区分总数奇偶

@pkookp8 Leetcode 004

@gbin 看了描述就回答了，没看到你的 ps 哈哈

考研 408 真题哈哈哈

应该考的是归并排序了，但是好像直接连接排序也没多慢

有序的话，也可以分类讨论下 nums2 是在 num1 的左边、中间还是右边，然后一次拼接上去

@lhx2008 二分查找哦

显然这题考的不是排序

'''java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length = nums1.length + nums2.length;
int[] nums = new int[length];
System.arraycopy(nums1,0,nums,0,nums1.length);
System.arraycopy(nums2,0,nums,nums1.length,nums2.length);
Arrays.sort(nums);
if (length % 2 == 0) {
return ((double)(nums[length/2] + nums[length/2 - 1]))/2;
} else {
return nums[length/2];
}
}
}

'''
emmm...输入复杂度最优，
提交了三次，最多可以 beats 85.52% (67 ms)

"""java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length = nums1.length + nums2.length;
int[] arr = new int[length];
int i = 0,j = 0; //nums1,nums2
for( int k = 0 ; k < length; k ++ ){
if( i >= nums1.length ){
arr[k] = nums2[j];
j ++;
}
else if( j >= nums2.length ){
arr[k] = nums1[i];
i ++;
}
else if(nums1[i] < nums2[j]){
arr[k] = nums1[i];
i ++;
}
else{
arr[k] = nums2[j];
j ++;
}
}
if (length % 2 == 0) {
return ((double)(arr[length/2] + arr[length/2 - 1]))/2;
} else {
return arr[length/2];
}
}
}
"""
不调系统函数耍流氓的方法，但是其实没有上面那个那么快，提交三次最快也就 68ms, beats 84%
一个原因是 System.arraycopy 是 jvm 实现的，比赋值快得多，Arrays.sort 也不慢
在 leetcode 上面也看了很多复杂的答案，但是至少在 leetcode 的测试用例来说，那一点时间复杂度优势相当于没有。当然其他情况不好说，要看什么地方用

题目都说了要 O(log(m+n))的做法了。排序应该是不行的。
有个 O(log(n+m))的做法是，在 nums1 二分查找一个数，二分判断其在 nums2 的位置，从而得知合并后它的位置，判断是否是中位数。

如果总长度是奇数
分别二分 num1 和 num2
对每个二分数 x 检查
num1 中小于 x 的数目+num2 中小于 x 的数目 是不是等于总长度的一半

如果总长度是偶数
二分 num1
然后取 num2 中与 num1 中的二分值相邻的两个数。
分别检查

我来实现一下一楼我说的方法吧，首先解决一个数组找中位数的问题
对于 len % 2 == 0，我们求出数组第 len / 2 大的数和 len / 2 + 1 大的数，再求和除以 2 就是中位数，对于 len % 2 == 1 的情况，直接找 len / 2 + 1 大的数就是中位数。
至于怎么求第 k 大的数（ top 问题），可以用快排的分区函数来实现。https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/



以下代码通过了 leetcode judege：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] cpy = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, cpy, 0, nums1.length);
System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length);
return findForOne(cpy);
}

double findForOne(int[] nums) {
if (nums.length % 2 == 0) {
int k1 = getKth(nums, 0, nums.length - 1, nums.length / 2);
int k2 = getKth(nums, 0, nums.length - 1, nums.length / 2 + 1);
return (k1 + k2) / 2.0;
}
return getKth(nums, 0, nums.length - 1, nums.length / 2 + 1);
}

int getKth(int[] nums, int lo, int hi, int k) {

int ans = Integer.MAX_VALUE;
if (k > 0 && k <= hi - lo + 1) {
int pos = partition(nums, lo, hi);
int len = pos - lo;

if (len == k - 1)
ans = nums[pos];
else if (k - 1 < len)
ans = getKth(nums, lo, pos - 1, k);
else
ans = getKth(nums, pos + 1, hi, k - len - 1);
}
return ans;
}

int partition(int arr[], int l, int r) {
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
}
}
int tmp = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
return i;
}
}

更新一下，上面的 top k 算法我摘自 geekforgeek 的，其实我并没有看懂。下面的找 top k 算法来自《算法 第四版》，这个代码更易读懂，运行时间也比上面的代码更短。

两个数组拼凑需要 O(m+n)，如果是偶数长度，查找两次 top k 需要 O(2*(m+n))，奇数长度 O(m+n)，因此时间复杂度在 O(2*(m+n))~O(3*(m+n))之间。
当然另一种方法是用两个指针指向两个数组当前元素，依次将当前最小的元素写入第三个数组，即合并两个有序数组生成的数组也是有序的。然后再找中位数。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] cpy = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, cpy, 0, nums1.length);
System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length);
return findForOne(cpy);
}

double findForOne(int[] nums) {
if (nums.length % 2 == 0) {
int k1 = getKth(nums, nums.length / 2 - 1);
int k2 = getKth(nums, nums.length / 2);
return (k1 + k2) / 2.0;
}
return getKth(nums, nums.length / 2);
}

//2 1 3 4 5
int getKth(int[] nums, int k) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int j = partition(nums, lo, hi);
if (j < k)
lo = j + 1;
else if (j > k)
hi = j - 1;
else {
return nums[k];
}
}
return nums[k];
}

int partition(int[] nums, int lo, int hi) {
int pivot = nums[lo];
int i = lo, j = hi + 1;

while (true) {
while (nums[++i] < pivot)
if (i == hi)
break;
while (nums[--j] > pivot)
if (j == lo)
break;
if (i >= j) break;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
int tmp = nums[lo];
nums[lo] = nums[j];
nums[j] = tmp;
return j;
}