问题描述：现在有m组n个有序数组，例如{1,2,3,4}，{2,3,4,6}，{1,3,5,7}，在这些数组中选择第k小的数据，然后返回这个值
思路：参照两个数组归并的过程，每次选取最小的数据进行比较
1，定义选取位置数组index[m]，初始化为0
2，每次根据index[m]寻找到第l_row个数组，确保当前时刻的第l_row数组的当前位置为最小值；寻找时确保index[i]的值小于n
3，把最小值取出，index[l_row]自增1
4，逐次寻找，知道找到第k个为止
public static int GetK_Min(int k)
{
int m=3,n=4;
if(k>m*n)
return -1;
int A[][] = {{1,3,5,6},{2,4,6,8},{1,2,4,6}}; int index[] = {0,0,0};
int l_min=0,l_row;
while(k>0)
{
for(int t=0;t<m;t++)
{
if(index[t]<n)
{l_min = A[t][index[t]];break;}
} l_min = 100;
l_row = 0;
for(int i=0;i<m;i++)
{
if(index[i]<n && l_min > A[i][index[i]])
{
l_min = A[i][index[i]];
l_row = i;
}
}
index[l_row] ++; k--;
} return l_min;
}
算法分析：
这个算法时间复杂度为O(k*m)，相比归并排序后再寻找时间复杂度较低