两个有序数组的上中位数和第K小数问题

哈，再介绍个操蛋的问题。当然，网上有很多解答，但是能让你完全看懂的不多，即便它的结果是正确的，可是解释上也是有问题的。

所以，为了以示正听，我也做了分析和demo，只要你愿意学习，你就一定能学会，并且不会有疑惑了。

可以侧面反映我的分析和算法都是逻辑严格，阐述清晰了。

————————————————————————————————————————————

原问题出于leetcode

Leetcode当然又是来源于实践了：对于两个有序的数组（升序），设A[]，长度m, B[]，长度为n, 如何找到第K小的数（此处根据中文语境做了处理，大多数资料都是照搬英文字面含义称为第K大数），当K为（m+n）/2时，结果就是上中位数。

我想在实际的应用领域中，估计会有这种需求出现，用最简单的两有序数组合并，然后自然得出需要的结果，时间复杂度接近于O(m+n)。而这个问题是存在O(log(m+n))时间复杂度的解决方案的，对于log级别的算法一定是二分查找，这里二分的类别就应该是有序的区间端。

解：第K小数

A，B两个数组，A的长度小于B，分别为m, n。如果m==0，则B[k-1]即为所求。1==K时，A[0]与B[0]中较小的那个即为所求。其它情况分析如下，取A数组的前num1个元素的子数组A1，再取B数组的前K-num1个元素的子数组B。我们设A1长度l1, B!长度l2。如果，B[l2-1]==A[l1-1]，A1和B1升序合并后应该改是…C[K-2],C[K-1]，其中C[k-2]==C[k-1]，值是A[l1-1]于B[l2-1]的其中之一，由于l1+l2==K，故而，我们找到了两个数组的第K小数就是C[K-1]，也即是A[l1-1]或者B[l2-1]；还剩下两种情况待分析，我们分别列出：

① A[l1-1]>B[l2-1]

此时，B可以分成两个子数组B[0…l2-1], B[l2...n-1]。这时候有一个关键问题需要理解，那就是B[0…l2-1]一定在第K小数序列之内，因为如果A[l1-1]就是第K小数的话，B[0…l2-1]的l2个元素一定在它之前，所以B[0…l2-1]中不存在第K小数，第K小数只能在B[l2…n-1]中，或者在A[0…l1-1]中出现，因为我们已经有l2个K小数之前的元素，只要在上两个数组中取出l1的小数，就可知道l2+l1=K, 也就是第A，B数组的第K小数求出。当然，A[0…l1-1]，B]l2…n-1]中的l1小数的求解也是一样的过程，这样就可以递归算法实现了。

② A[l1-1]<B[l2-1]

与上一种情况是互补的，所以很容易分析出。

算法

//array2k.c

#include <stdio.h>

#include <stdlib.h>

#include <error.h>

#include <string.h>

int find2k(int array1[], int len1, int array2[], int len2, int k)

{

if (k<0)

{

fprintf(stderr, "k value is no ligal\n");

return -1;

}

// make sure len1<=len2

if (len1>len2)

{

return find2k(array2, len2, array1, len1, k);

}

// return condition

if (0==len1)

{

return array2[k-1];

}

if (1==k)

{

return array1[0]>=array2[0]?array2[0]:array1[0];

}

// num1+num2==k

int num1 = len1>=k/2?k/2:len1;

int num2 = k-num1;

if (array1[num1-1]==array2[num2-1])

{

return array1[num1-1];

}

else if (array1[num1-1]>array2[num2-1])

{

return find2k(array1, num1, &array2[num2], len2-num2, k-num2);

}

else

{

return find2k(&array1[num1], len1-num1, array2, num2, k-num1);

}

//test.c

#include "array2k.h"

#include <stdio.h>

#include <stdlib.h>

#include <error.h>

#include <string.h>

void main()

{

int array1[11] = {10,21,22,35,47,56,67};

int array2[11] = {33,44,55,63,72,83};

// 7==k

int ret = find2k(array1, 7, array2, 6, 7);

printf("7==k, %d\n", ret);

//k==(7+6)/2, mid number

ret = find2k(array1, 7, array2, 6, 6);

printf("6==k(mid number), %d\n", ret);

}

//result:

# ./test

7==k, 47

6==k(mid number), 44

Finally:

这两个问题是普遍和特性问题，应该是上中位问题是是第K小数问题的特例，而不是网上有些人说的用特列之上中位来求第K小数，哪里的分析我也看了，云里雾里得，因为它的前提就错了。

有序数组的最低时间复杂度的排序和查找问题，应该是实际工程中比较重要的算法需求，所以，这个问题还是请重视一下。

巴特西

两个有序数组的上中位数和第K小数问题

最新文章

热门文章