0

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

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

我想到的想法：
1.维护一个最小堆，但是我需要扫描所有剩余数组的所有元素吗？
2. 维护 op 大小为 K 的数组，然后扫描所有数组的所有元素，除非我们在数组 "op" 中遇到大于 max 的元素

如果我从专栏开始思考，有什么办法吗？

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

4

4 回答 4

1

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

编辑：关于合并的修改后：

另一种解决方案是迭代 k 次，并找到每个数组的第一个元素的最小值（即，如果您有数组 [1、2、3、4、5]、[2、4、6] 和 [3 , 4, 7, 8]，你会找到 min(1, 2, 3)。将此最小值添加到您的解决方案数组（k 个最小整数）中，并将其从相应的数组中删除。

于 2013-01-18T23:11:11.950 回答
1

这可能会给你一个想法..

         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-18T23:22:35.443 回答
0

另一种方法是像堆栈一样使用数组。您需要在每个数组中保存一个指向上次使用的最小值的指针，并在每次迭代时检查所有指针（在您的示例中为 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-18T23:17:27.113 回答
0

一种方法是

使用 将所有已排序的数组收敛为一个已排序的数组，然后答案是新数组开头的 k 个元素。为此，您可以通过从开始维护每个数组的索引并在该数组中的元素被推入结果数组时递增它们来实现。我已经为两个数组做了这个，你可以进一步使用它。

添加约束后编辑：遍历所有数组，如果任何数组的长度> 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-18T23:10:22.577 回答