从n个排序数组中找出k个最小数字

我有n个排序不同大小的数组。给K我需要找到前k个最小的数字。
int a [] = {10,20,30,40};
int b [] = {20,30,40};
int c [] = { - 10,0};
从n个排序数组中找出k个最小数字

如果k = 1，那么输出应该是数组= {-10}，k = 2然后op = {-10,0} k = 4 {-10,0,10,20,20}

想法，我认为的：
1.保持最小堆，但我需要扫描所有剩余的阵列中的所有元素？
2.保持大小为K的运算数组，然后扫描所有的阵列中的所有元素，除非我们阵中的“OP”比最大遇到的元素更大

有什么办法如果我开始从列在想什么？

约束条件：合并所有数组并找到第一个k并不好，因为数组的大小可能很大，就像单个数组中的百万个整数一样。

来源

2013-01-18 mcmattu

新增的约束部分。 – mcmattu

我在添加约束后修改了我的回复;只是抬起头来。 –

一种方法是

汇合所有排序阵列成使用单个排序后的数组，然后回答为从所述新的数组的开始的k个元素。这样做可以通过为每个数组的索引维护一个索引来实现，并在数组中的某个元素被推送到结果数组中时对其进行递增。我已经完成了两个数组，你可以进一步使用它。

EDIT后约束添加：通过所有阵列去，并且如果任何具有长度> K，截断为长度为k（这可能是一个较好的折衷如果每个是一个大阵列）

// Find K largest numbers in two sorted arrays 
//Returns 0 on success and -1 in failure and c contains the resulting array 


int k_largest(a, b, c, k) { 
    int a_len = a.length; 
    int b_len = b.length; 
    if (a_len + b_len < k) return -1; 
    int i = 0; 
    int j = 0; 
    int m = 0; 

if(a[k] < b[0]) 
c=a; 
else if (b[k] < a[0]) 
c=b; 

/* (i<k) test below is to discard the rest of the elements of the arrays , 
using the sorted property of array */ 

    while (i < k && j < a_len && m < b_len) { 
     if (a[j] < b[m]) { 
      c[i] = a[j]; 
      i++; 
      j++; 
     } else { 
      c[i] = b[m]; 
      i++; 
      m++; 
     } 
    } 

    if (i === k) { 
     return 0; 
    } else if (j < a_len) { 
     while (i < k) { 
      c[i++] = b[m++]; 
     } 
    } else { 
     while (i < k) c[i++] = a[j++]; 
    } 
    return 0; 
}

执行此再次，其中a =所得阵列且b =第三阵列等

来源

2013-01-18 23:10:22

1000个数组的大小1,2,3 1,2,3 ...1000，并且只考虑最后一个数组中的所有元素都是“-1”。在你的100个最小元素的解决方案中，你需要不经意地合并前999个数组。 – mcmattu

@ winuser123回答编辑。至少你必须测试每个数组的k个元素。否则，您应该修改上述相同的算法以使用二分查找。找到方向上的变化点。 –

使用基本的合并（例如在合并排序）将在O（米）运行时间（其中，m是元件的总数），和从那里你可以选择前k个元素。

编辑：你的有关合并ammendment后：

另一解决方案是迭代k次，并找出最小的每个阵列的第一元件（的即，如果你有阵列[1，2，3， 4，5]，[3,4,6]和[3,4,7,8]，你可以找到min（1,2,3）。），并将它从相应的数组中移除

来源

2013-01-18 23:11:11

另一种方法是使用你的数组，像堆栈一样，你需要在每个数组中保存一个指向最后使用的最小值的指针并检查所有指针（在你的例子中是3个指针），每次迭代都需要进行K次迭代才能得到K值

这里是C＃示例代码：

int[] a = new int[] {10,20,30,40}; 
int[] b = new int[] {20,30,40}; 
int[] c = new int[] {-10,0}; 

Dictionary<object, int> dic = new Dictionary<object, int>(); 
dic.Add(a, 0); 
dic.Add(b, 0); 
dic.Add(c, 0); 

int K = 4; 

for (int i = 0; i < K; i++) 
{ 
    var min = dic.Min(s => ((int[])s.Key)[s.Value]); 
    var arr = dic.First(p => ((int[])p.Key)[p.Value] == min); 
    int idx = arr.Value + 1; 
    dic.Remove(arr.Key); 
    if (((int[])arr.Key).Length > idx) 
     dic.Add(arr.Key, idx); 
    Console.WriteLine(min); 
}

来源

2013-01-18 23:17:27 Anthony

这可能给你一个想法..

  List<int> new1 = new List<int>(); 
     List<int> testArr = new List<int>() { 10, 20, 30, 40 }; 
     List<int> testArr1 = new List<int>() { -10, 0 }; 
    int[] newArr= testArr.Concat(testArr1).ToArray(); 

    var s1 = (from i in newArr 
       orderby i ascending 
       select i); 
    foreach (var x in s1) 
    { 
     new1.Add(x); 
    }

来源

2013-01-18 23:22:35

从n个排序数组中找出k个最小数字

回答

相关问题