最近我在C#中遇到了一个问题:
有三个int数组
Array1={88,65,09,888,87}
Array2={1,49,921,13,33}
Array2={22,44,66,88,110}
现在我需要从这三个数组中获取最高的5个元素组成的数组。在C#中,最优化的实现方式是什么?
我能想到的一种方法是创建一个大小为15的数组,并将三个数组的所有元素添加到该数组并进行排序,然后取出最后5个。
最近我在C#中遇到了一个问题:
有三个int数组
Array1={88,65,09,888,87}
Array2={1,49,921,13,33}
Array2={22,44,66,88,110}
现在我需要从这三个数组中获取最高的5个元素组成的数组。在C#中,最优化的实现方式是什么?
我能想到的一种方法是创建一个大小为15的数组,并将三个数组的所有元素添加到该数组并进行排序,然后取出最后5个。
对于固定的 K=5
,最优化的方法是五次遍历所有数组,在每次遍历中选择目前未被选择的最高元素。您需要标记您所选取的元素以便在后续遍历中跳过它。这个方法的时间复杂度为 O(N1+N2+N3)
(您需要五次遍历所有 N1+N2+N3
个元素),这已经是最快的速度了。
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);
}
}
}
}
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。
这里有两种方法可以完成这个任务。第一种方法是仅使用基本类型。这是最有效的方式,没有额外的循环、比较或内存消耗。您只需要传递需要匹配的元素索引,并计算给定数组中下一个要匹配的索引是哪个。
第一种方法 -
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个元素的数组,这将是“最大值”数组。
最初用前5个值填充它,这在你的情况下只是第一个数组。然后循环遍历其余的值。对于每个值,从最小到最大检查它与5个最大值的值。如果你发现主列表中的当前值大于最大值数组中的值,则将其插入到该元素上方的数组中,这将推出最后一个元素。最后,你应该有一个包含5个最大值的数组。
对于长度为N1、N2、N3的三个数组,最快的方法应该是将这三个数组合并,然后使用修改后的快速排序算法找到第(N1+N2+N3-4)个顺序统计量。
在结果数组中,索引为(N1+N2+N3-5)到最大值(N1+N2+N3-1)的元素应该是您的五个最大值。您也可以稍后对它们进行排序。
这种方法的时间复杂度平均为O(N1+N2+N3)。
简短回答:在.NET中使用SortedList和Sorted Collection Types作为最小堆。
解释:
复杂度:当您拥有k个元素的SortedList时,需要Log k时间才能找到最小值。将其乘以所有数组中的总元素数,因为您将执行这么多次“查找最小操作”。
这带我们到整体复杂度为O(n * Log k),其中n是您所有数组中的元素总数,k是您想要的最高数字的数量。