CODEWITHSUNDEEP
c#arraysalgorithmlinq
theateist
theateist

Reputation: 14421

How to return arrays with the biggest elements in C#?

I have multiple int arrays:

1) [1 , 202,4  ,55]
2) [40, 7]
3) [2 , 48 ,5]
4) [40, 8  ,90]

I need to get the array that has the biggest numbers in all positions. In my case that would be array #4. Explanation:

Can you suggest an efficient algorithm for this? Doing with Linq will be preferable.

UPDATE

There is no limitation for the length, but as soon as some number in any position is greater, so this array is the biggest.

Upvotes: 5

Views: 945

Answers (7)

maximpa
maximpa

Reputation: 1998

var allArrays = new[]
{
    new[] { 1, 202, 4, 55 },
    new[] { 40, 7 },
    new[] { 2, 48, 5 },
    new[] { 40, 8, 90 }
};

Find the indexes to compare.

Exclude 3rd index, because there is nothing to compare, i.e. only 55 in the 1st array:

Data

var maxElementsCount = allArrays.GroupBy(p => p.Length)
    // Find 2 at least
    .Where(p => p.Count() > 1)
    // Get the maximum
    .OrderByDescending(p => p.Count())
    .First().Key;

// 0, 1, 2
var indexes = Enumerable.Range(0, maxElementsCount);

Get the slices:

Slices table

var slices = indexes.Select(i =>
    allArrays.Select((array, arrayNo) => new
    {
        ArrayNo = arrayNo,
        // null if the element doesn't exist
        Value = i < array.Length ? array[i] : (int?)null
    }))
    .ToArray();

Slices

// Get the max values in each slice
var maxValues = slices.SelectMany(slice =>
    {
        var max = slice.Max(i => i.Value);
        return slice.Where(i => i.Value == max);
    })
    .ToArray();

Max values

// Get the result array no
var arrayNumber = maxValues.GroupBy(p => p.ArrayNo)
    .OrderByDescending(p => p.Count())
    .First().Key;

var res = allArrays[arrayNumber];

Result

Upvotes: 1

L.B
L.B

Reputation: 116188

a) Not an *efficient* one, but easy to write one-liner.

var arr1 = new int[] { 1, 202, 4, 55 };
var arr2 = new int[] { 40, 7 };
var arr3 = new int[] { 2, 48, 5 };
var arr4 = new int[] { 40, 8, 90 };

var max = new int[][] { arr1, arr2, arr3, arr4 }
           .Select(arr => new { 
                   IArray = arr, 
                   SArray = String.Join("",arr.Select(i => i.ToString("X8"))) 
           })
           .OrderByDescending(x => x.SArray)
           .First()
           .IArray;

b) A better one by implementing `IComparer`

public class ArrayComparer : IComparer<int[]>
{
    public int Compare(int[] x, int[] y)
    {
        for(int i=0;i < Math.Min(x.Length,y.Length);i++)
        {
            if (x[i] > y[i]) return 1;
            if (x[i] < y[i]) return -1;
        }
        return x.Length - y.Length;
    }
}

var max2 = new int[][] { arr1, arr2, arr3, arr4 }
           .OrderByDescending(x => x, new ArrayComparer())
           .First();

c) The best one

var arrays = new int[][] { arr1, arr2, arr3, arr4 };
var max3 = arrays[0];
ArrayComparer comparer = new ArrayComparer();
for (int i = 1; i < arrays.Length; i++)
{
    if(comparer.Compare(arrays[i],max3)>0) max3 = arrays[i];
}

d) A Generic version by extending "Max" 

var max4 = new int[][] { arr1, arr2, arr3, arr4 }
            .Max(new SOExtensions.Comparer<int>())
            .ToArray();

public static class SOExtensions
{
    public static IEnumerable<T> Max<T>(this IEnumerable<IEnumerable<T>> lists, IComparer<IEnumerable<T>> comparer)
    {
        var max = lists.First();
        foreach (var list in lists.Skip(1))
        {
            if (comparer.Compare(list, max) > 0) max = list;
        }
        return max;
    }

    public class Comparer<T> : IComparer<IEnumerable<T>> where T: IComparable<T>
    {
        public int Compare(IEnumerable<T> x, IEnumerable<T> y)
        {
            foreach(var ab in  x.Zip(y,(a,b)=>new{a,b}))
            {
                var res=ab.a.CompareTo(ab.b);
                if (res != 0) return res;
            }
            return x.Count() - y.Count();
        }
    }
}

Conclusion

Their relative performances in my test case: 4000T, 270T, T, 6T

So, If you are looking for speed, don't use an algorithm that makes use of Sort/OrderBy, Since its cost is O(N*Log(N)) (while Max is O(N))

Upvotes: 1

Lukas Winzenried
Lukas Winzenried

Reputation: 1919

Looks like a problem that can be solved with a recursion.

public void GetMax()
{
    var matrix = new[]
                {
                    new[] {1, 202, 4, 55},
                    new[] {40, 7},
                    new[] {2, 48, 5},
                    new[] {40, 8, 90}
                };
    var result = GetMaxRecursive(matrix).FirstOrDefault();
}

private static int[][] GetMaxRecursive(int[][] matrix, int level = 0)
{
    // get max value at this level
    var maxValue = matrix.Max(array => array.Length > level ? int.MinValue : array[level]);

    // get all int array having max value at this level
    int[][] arraysWithMaxValue = matrix
        .Where(array => array.Length > level && array[level] == maxValue)
        .ToArray();

    return arraysWithMaxValue.Length > 1
                ? GetMaxRecursive(arraysWithMaxValue, ++level)
                : arraysWithMaxValue;
}

Upvotes: 0

nawfal
nawfal

Reputation: 73311

Something without Linq at all:

public static List<int[]> FindTheHighestArrays(List<int[]> lst)
{
    List<KeyValuePair<int[], int>> temp = new List<KeyValuePair<int[], int>>();
    List<int[]> retList = lst;
    lst.Sort((x, y) => x.Length.CompareTo(y.Length));
    int highestLenght = lst[lst.Count - 1].Length;
    for (int i = 0; i < highestLenght; i++)
    {
        temp.Clear();

        foreach (var item in retList)
        {
            if (item.Length <= i)
                continue;

            temp.Add(new KeyValuePair<int[], int>(item, item[i]));
        }

        temp.Sort((x, y) => x.Value.CompareTo(y.Value));
        retList.Clear();
        retList.AddRange(temp.FindAll(kvp => kvp.Value == temp[temp.Count - 1].Value).ConvertAll(f => f.Key));

        if (retList.Count == 1)
            return retList;
    }

    return retList;
}

The above function returns a list of int arrays which are highest. For instance if you try,

1) [1, 202, 4, 55]

2) [1, 202, 4, 55]

the function returns both arrays since they both are equally highest. If you want only one array in such cases, then its just a matter of changing the return type and returning the first element of the list.

You can call it like:

int[] a = new int[] { -1, 31, 90 };
int[] b = new int[] { -1, 31, 89 };
int[] c = new int[] { 0, 0, 90 };
List<int[]> lst = new List<int[]>() { a, b, c };

var highestArrays = FindTheHighestArrays(lst);

Upvotes: 0

AlexSavAlexandrov
AlexSavAlexandrov

Reputation: 873

I would suggest "Binary search trees". It allows fast access to the minimum and maximum element.

http://en.wikipedia.org/wiki/Binary_search_tree

You will need one tree for each array, and one tree that combines the arrays.

You can also search for "Red-Black BST" algorithm for easy optimization of the trees if you are planning to make them bigger.

EDIT:

Normal BSTs are fast on their own, but the trees become quite unbalanced when adding elements- for example: if the value of every newly added variable is, on average, bigger than the previous one, the path to the maximum will get longer and longer, while the path to the minimum will remain really short. Red-Black BSTs are balanced- the paths to the most distant elements (min and max included) remain equally short. There is a faster type of BSTs, but as far as I know, they are difficult to code.

But if you are going to use Red-Black BSTs, I suggest that you first master the usual BSTs.

Upvotes: 0

Adam Kostecki
Adam Kostecki

Reputation: 301

I would go for a traditional object oriented approach and create a wrapper:

public class SpecialArray<T> : IComparable<SpecialArray<T>>
    where T : IComparable
{
    public T[] InternalArray { get; private set; }

    public SpecialArray(T[] array)
    {
        InternalArray = array;
    }

    public int CompareTo(SpecialArray<T> other)
    {
        int minLength = Math.Min(InternalArray.Length, other.InternalArray.Length);

        for ( int i = 0; i < minLength; i++ )
        {
            int result = InternalArray[i].CompareTo(other.InternalArray[i]);

            if ( result != 0 )
                return result;
        }

        return 0;
    }
}

then you can search for max like this:

        var list = new[]
            {
                new SpecialArray<int>(new[] {1, 202, 4, 55}),
                new SpecialArray<int>(new[] {40, 7}),
                new SpecialArray<int>(new[] {2, 48, 5}),
                new SpecialArray<int>(new[] {40, 8, 90})
            };

        var max = list.Max();

Upvotes: 0

Tim S.
Tim S.

Reputation: 56586

LINQ is not very efficient (e.g. see LINQ vs FOREACH vs FOR). However, it allows for great readability. If you actually need better performance than LINQ provides, you should write the code without LINQ. However, you shouldn't do optimizations before you know they're needed.

This is not specifically tuned for performance, but is a clear, readable solution to your problem:

static int[] FindLargestArray(int[][] arrays)
{
    for (int i = 0; arrays.Length > 1 && i < arrays.Max(x => x.Length); i++)
    {
        var maxVal = arrays.Where(x => i < x.Length).Max(x => x[i]);
        arrays = arrays.Where(x => i < x.Length && x[i] == maxVal).ToArray();
    }
    return arrays[0]; //if more than one array, they're the same, so just return the first one regardless
}

Depending on the circumstance, the performance of this may well be good enough.

Upvotes: 1

Related Questions