问题描述:现在有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个为止
1 public static int GetK_Min(int k) 2 { 3 int m=3,n=4; 4 if(k>m*n) 5 return -1; 6 int A[][] = {{1,3,5,6},{2,4,6,8},{1,2,4,6}}; 7 8 int index[] = {0,0,0}; 9 int l_min=0,l_row; 10 while(k>0) 11 { 12 for(int t=0;t<m;t++) 13 { 14 if(index[t]<n) 15 {l_min = A[t][index[t]];break;} 16 } 17 18 l_min = 100; 19 l_row = 0; 20 for(int i=0;i<m;i++) 21 { 22 if(index[i]<n && l_min > A[i][index[i]]) 23 { 24 l_min = A[i][index[i]]; 25 l_row = i; 26 } 27 } 28 index[l_row] ++; 29 30 k--; 31 } 32 33 return l_min; 34 }
算法分析:
这个算法时间复杂度为O(k*m),相比归并排序后再寻找时间复杂度较低
现在有m组n个有序数组,例如{1,2,3,4},{2,3,4,6},{1,3,5,7},在这些数组中选择第k小的数据,然后返回这个值
原文:http://www.cnblogs.com/justinjia/p/3980177.html