三个给定数组中的前五个值

Question

最近我在C#中遇到了一个问题：

有三个int数组

Array1={88,65,09,888,87}

Array2={1,49,921,13,33}

Array2={22,44,66,88,110}

现在我需要从这三个数组中获取最高的5个元素组成的数组。在C#中，最优化的实现方式是什么？

我能想到的一种方法是创建一个大小为15的数组，并将三个数组的所有元素添加到该数组并进行排序，然后取出最后5个。

- F11

---

你可以有重复吗？例如，如果Array1和Array2都有相同的数字，并且它也是最大的数字。 - Inisheer

@jamylak：如果5个最高值都存储在三个数组之一中，该怎么办？ - Jack

@Jack 哦，好的，那就算了。在这种情况下，只需对所有数组使用快速选择来查找第6大的数字，并使用比枢轴更高的数字。如果始终是前5个数字且不会改变，则可以使用更简单的方法。 - jamylak

@inisheer，是的，它可以有重复项。 - F11

你想要为自己的努力优化，还是为机器的努力优化？ - Kirk Broadhurst

Answer 1

对于固定的 K=5 ，最优化的方法是五次遍历所有数组，在每次遍历中选择目前未被选择的最高元素。您需要标记您所选取的元素以便在后续遍历中跳过它。这个方法的时间复杂度为 O(N1+N2+N3) （您需要五次遍历所有 N1+N2+N3 个元素），这已经是最快的速度了。

- Sergey Kalinichenko

---

不确定是否可以更快地完成。可以在一次遍历中完成，保持一个已排序的数组，其中包含5个当前最高的值，并在迭代期间检查原始数组中的每个值是否与5个最高临时数组中的最低值相同，必要时进行更新。鉴于数组的常数大小，排序和检查并不会增加复杂性。甚至可能减少实际运行算法所需的时间，因为这样它在平均情况下不需要为所有值执行5个操作。 - G. Bach

你的错误答案来找你了。 :) 我提供了一个优化的解决方案。在任何给定的一天，_5 * (N1 + N2 + N3) > (Log 5) * (N1 + N2 + N3)_。 - displayName

Answer 2

LINQ提供了一种简单的方法：

int[] top5 = array1.Concat(array2).Concat(array3).OrderByDescending(i => i).Take(5).ToArray();

一种最佳方法：

 List<int> highests = new List<int>(); // Keep the current top 5 sorted
 // Traverse each array. No need to put them together in an int[][]..it's just for simplicity
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i); // where should i be?

         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         }
         else if (index < 0) { // not in top-5 yet, add
             highests.Insert(~index, i);
             highests.RemoveAt(0);
         } else if (index > 0) { // already in top-5, add (duplicate)
             highests.Insert(index, i);
             highests.RemoveAt(0);
         }
     }
 }

请保持一个有序的前5个元素列表，并且只需遍历每个数组一次。

您甚至可以每次检查前5个元素中的最小值，避免进行二进制搜索：

 List<int> highests = new List<int>();
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i);
         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {                    
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         } else if (highests.First() < i) { // if larger than lowest top-5                
             if (index < 0) { // not in top-5 yet, add
                highests.Insert(~index, i);
                highests.RemoveAt(0);
             } else { // already in top-5, add (duplicate)
                highests.Insert(index, i);
                highests.RemoveAt(0);
             }
         }
     }
}

- Julián Urbano

---

显然这是一种简单的方法，但它是否是最优化的方法呢？它的工作方式与将三个数组的所有成员添加到一个新数组中，然后对其进行排序相同。 - F11

Answer 3

你可以使用LINQ组合数组，对它们进行排序，然后反转。

    int[] a1 = new int[] { 1, 10, 2, 9 };
    int[] a2 = new int[] { 3, 8, 4, 7 };
    int[] a3 = new int[] { 2, 9, 8, 4 };

    int[] a4 = a1.Concat(a2).Concat(a3).ToArray();

    Array.Sort(a4);
    Array.Reverse(a4);

    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine(a4[i].ToString());
    }
    Console.ReadLine();

根据我提供的数组样本，输出为10、9、9、8、8。

- Inisheer

---

就复杂度而言，排序是一种不好的方法。但是，根据输入的大小，优化对数可能并不重要。 - G. Bach

@G.Bach 正确。我本来想编辑答案，但是caerolus已经回答了我要做的修改。我不想从他那里夺走任何被认为属于他的功劳。 - Inisheer

显然这是一种简单的方法，但它是否是最优化的方法呢？它的工作方式与将三个数组的所有成员添加到一个新数组中，然后对其进行排序相同。 - F11

@litte 你说得对。有时候我认为展示100%优化的方式可能会导致答案不清晰。但是优化确实有价值。此外，有时候并不一定需要使用优化的方式。在这种情况下，根据OP的问题和示例，我认为并不需要。如果他/她发布了数组将包含更多元素的信息，则需要采用不同的方法。 - Inisheer

@Inisheer：没关系 :-) 无论如何，我编写的LINQ代码与您的相同，但是按降序排序。不够高效。现在我添加了一种高效的解决方法。 - Julián Urbano

Answer 4

这里有两种方法可以完成这个任务。第一种方法是仅使用基本类型。这是最有效的方式，没有额外的循环、比较或内存消耗。您只需要传递需要匹配的元素索引，并计算给定数组中下一个要匹配的索引是哪个。

第一种方法 -

http://www.dotnetbull.com/2013/09/find-max-top-5-number-from-3-sorted-array.html

第二种方式 -

int[] Array1 = { 09, 65, 87, 89, 888 };
int[] Array2 = { 1, 13, 33, 49, 921 };
int[] Array3 = { 22, 44, 66, 88, 110 };

int [] MergeArr = Array1.Concat(Array2).Concat(Array3).ToArray();
Array.Sort(MergeArr);
int [] Top5Number = MergeArr.Reverse().Take(5).ToArray() 

取自 -

从三个已排序的数组中找出前5个最大的数字

- Vivek

Answer 5

也许你可以有一个包含5个元素的数组，这将是“最大值”数组。

最初用前5个值填充它，这在你的情况下只是第一个数组。然后循环遍历其余的值。对于每个值，从最小到最大检查它与5个最大值的值。如果你发现主列表中的当前值大于最大值数组中的值，则将其插入到该元素上方的数组中，这将推出最后一个元素。最后，你应该有一个包含5个最大值的数组。

- Feles

Answer 6

对于长度为N1、N2、N3的三个数组，最快的方法应该是将这三个数组合并，然后使用修改后的快速排序算法找到第(N1+N2+N3-4)个顺序统计量。

在结果数组中，索引为(N1+N2+N3-5)到最大值(N1+N2+N3-1)的元素应该是您的五个最大值。您也可以稍后对它们进行排序。

这种方法的时间复杂度平均为O(N1+N2+N3)。

- SidR

Answer 7

简短回答：在.NET中使用SortedList和Sorted Collection Types作为最小堆。

---

解释：

1. 从第一个数组中，将5个元素添加到这个SortedList/min-heap中；
2. 现在遍历所有其他数组的元素：
   • 如果一个数组元素比min-heap中最小的元素大，则删除最小元素并将此数组元素推入堆中；
   • 否则，继续下一个数组元素；
3. 最后，您的min-heap具有所有数组中最大的5个元素。

---

复杂度：当您拥有k个元素的SortedList时，需要Log k时间才能找到最小值。将其乘以所有数组中的总元素数，因为您将执行这么多次“查找最小操作”。

这带我们到整体复杂度为O(n * Log k)，其中n是您所有数组中的元素总数，k是您想要的最高数字的数量。

- displayName