c# - 来自三个给定数组的前 5 个值

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 个。

Answer 1

最优化的固定方法K=5是遍历所有数组五次，每次通过时选择迄今为止未采用的最高元素。您需要标记您采取的元素，以便在后续通过时跳过它。这具有O(N1+N2+N3)（您遍历所有N1+N2+N3元素五次）的复杂性，这是尽可能快的。

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 名中的最低值，避免使用 BinarySearch：

 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);
             }
         }
     }
}

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();

Prints: 10, 9, 9, 8, 8 来自我作为数组输入提供的样本。

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 个数字

Answer 5

对于长度为 N1,N2,N3 的三个数组，最快的方法应该是合并 3 个数组，然后使用改进的快速排序找到 (N1+N2+N3-4) 阶统计量。

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

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

Answer 6

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

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

Answer 7

简短的回答：使用.NET中排序集合类型中的排序列表作为最小堆。

---

解释：

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

---

复杂性：当您有一个包含 k 个元素的 SortedList 时，需要 Log k 时间来找到最小值。将其乘以所有数组中的总元素，因为您将多次执行此“查找最小操作”。

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