两个有序数组的上中位数和第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小数,哪里的分析我也看了,云里雾里得,因为它的前提就错了。

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

上一篇:PAT甲级专题|链表


下一篇:C# 链表去重 List 一维 二维 分别使用 Distinct() GroupBy() 方法