Top 5 values ​​from three given arrays

Question

I recently ran into a question in C #, question: - There are three int arrays

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

array2 = {1.49,921,13,33}

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

Now I need to get an array of the highest 5 of all three of these arrays. What is the most optimized way to do this in C #?

The way I can think of is to take an array of size 15 and add array elements from all three arrays and sort it, get the last 5.

Answer 1

A simple way with LINQ:

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

The best way:

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

Keep the sorted top-level list of 5 and move each array only once.

You can even check the lowest of the top 5 each time, avoiding 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 2

The most optimized way for a fixed K=5 is to go through all the arrays five times, choosing the highest element that has not been received so far in each pass. You need to mark the item that you take in order to skip it in subsequent passes. This has complexity O(N1+N2+N3) (you go through all the N1+N2+N3 elements five times), which is as fast as it can be.

Answer 3

You can combine arrays with LINQ, sort them, and then drop them.

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

Fingerprints: 10, 9, 9, 8, 8 from sample I, provided as input for arrays.

Answer 4

Perhaps you can have an array of 5 elements, which will be an array of "max values".

Initially, fill it with the first 5 values, which in your case will be only the first array. Then skip the rest of the values. For each value, check it for 5 maximum values ​​from smallest to largest. If you find that the current value from the main list is greater than the value in the array of maximum values, insert it above this element into the array that pops the last element. At the end, you should have an array of 5 maximum values.

Answer 5

For three arrays of length N1, N2, N3, the fastest way is to combine the three arrays, and then search for statistics (N1 + N2 + N3-4) of the th order using modified quick sorting.

In the resulting array, elements with indices (N1 + N2 + N3-5) to the maximum (N1 + N2 + N3-1) should be your 5 largest. You can also sort them later.

The time complexity of this approach is O (N1 + N2 + N3) on average.

Answer 6

Here are two ways to accomplish this task. The first uses only basic types. This is the most effective way, without an additional cycle, without additional comparison and additional memory consumption. You simply pass in the index of the elements that should be mapped to another, and calculate which next index should be mapped for each given array.

The first way is

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

The second way is

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

Taken from -

Find the maximum number 5 of three sorted arrays

Answer 7

Short answer: Use the SortedList from Sorted Collection Types in .NET as a mini-heap.

---

Explanation:

• From the first array, add 5 elements to this SortedList / min-heap;
• Now iterate over all the other elements of the arrays:
  • If the array element is larger than the smallest element in min-heap, then remove the min element and push this array element into the heap;
  • Repeat, go to the next element of the array;
• After all, your mini-heap has the 5 largest elements of all arrays.

---

Difficulty: It takes time k to find the minimum value when you have a SortedList of k elements. Multiply this by the total elements in all arrays, because you are going to perform this “minimum operation search” many times.

Brings us the overall complexity of O (n * Log k), where n is the total number of elements in all your arrays, and k is the number of the highest numbers you want.