Top 5 values from three given arrays

Question

Recently i faced a question in C#,question is:- 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 have to get array of highest 5 from all these three arrays.What is the most optimized way of doing this in c#?

The way i can think of is take an array of size 15 and add array elements of all three arrays and sort it n get last 5.

Answer 1

An easy way with LINQ:

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

An optimal 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'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);
         }
     }
 }

Keep a sorted list of the top-5 and traverse each array just once.

You may even check the lowest of the top-5 each time, avoiding the 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 gong through all arrays five times, picking the highest element not taken so far on each pass. You need to mark the element that you take in order to skip it on subsequent passes. This has the complexity of O(N1+N2+N3) (you go through all N1+N2+N3 elements five times), which is as fast as it can get.

Answer 3

You can combine the arrays using LINQ, sort them, then reverse.

    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 from the sample I provided as input for the arrays.