首页 > 代码库 > 现在有m组n个有序数组，例如{1,2,3,4}，{2,3,4,6}，{1,3,5,7}，在这些数组中选择第k小的数据，然后返回这个值
现在有m组n个有序数组，例如{1,2,3,4}，{2,3,4,6}，{1,3,5,7}，在这些数组中选择第k小的数据，然后返回这个值
问题描述：现在有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小的数据，然后返回这个值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。