CODEWITHSUNDEEP
c#.netalgorithmlinq
user6048670
user6048670

Reputation: 2887

How can I make my procedure for finding the Nth most frequent element in an array more efficient and compact?

Here's an example of a solution I came up with

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        int[] arr = new int[] { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 }; 
        var countlist = arr.Aggregate(new Dictionary<int,int>(), (D,i) => { 
                                        D[i] = D.ContainsKey(i) ? (D[i] + 1) : 1;
                                        return D; 
                                      })
                            .AsQueryable()
                            .OrderByDescending(x => x.Value)
                            .Select(x => x.Key)
                            .ToList();
        // print the element which appears with the second 
        // highest frequency in arr
        Console.WriteLine(countlist[2]); // should print 3
    }
}

At the very least, I would like to figure out how to

Upvotes: 2

Views: 3845

Answers (4)

pijemcolu
pijemcolu

Reputation: 2605

I came up with the the following mash of Linq and a dictionary as what you're looking for is essentialy an ordered dictionary

        void Run()
    {
        int[] arr = new int[] { 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4 };
        int[] unique = arr.Distinct().ToArray();
        Dictionary<int, int> dictionary = unique.ToDictionary(k => k, v => 0);

        for(int i = 0; i < arr.Length; i++)
        {
            if(dictionary.ContainsKey(arr[i]))
            {
                dictionary[arr[i]]++;
            }
        }

        List<KeyValuePair<int, int>> solution = dictionary.ToList();
        solution.Sort((x,y)=>-1* x.Value.CompareTo(y.Value));
        System.Console.WriteLine(solution[2].Key);
    }

Upvotes: 1

Gary Holland
Gary Holland

Reputation: 2645

I started to answer, saw the above answers and thought I'd compare them instead.

Here is the Fiddle here.

I put a stopwatch on each and took the number of ticks for each one. The results were:

Orignal: 50600
Berkser: 15970
Tommy: 3413
Hari: 1601
user3185569: 1571

It appears @user3185569 has a slightly faster algorithm than Hari and is about 30-40 times quicker than the OP's origanal version. Note is @user3185569 answer above it appears his is faster when scaled.

update: The numbers I posted above were run on my pc. Using .net fiddle to execute produces different results:

Orignal: 46842
Berkser: 44620
Tommy: 11922
Hari: 13095
user3185569: 16491

Putting the Berkser algortihm slightly faster. I'm not entirely clear why this is the case, as I'm targeting the same .net version.

Upvotes: 1

Hari Prasad
Hari Prasad

Reputation: 16956

I would do this.

int[] arr = new int[] { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 }; 


int rank =2; 
var item = arr.GroupBy(x=>x)          // Group them
   .OrderByDescending(x=>x.Count())   // Sort based on number of occurrences
   .Skip(rank-1)                      // Traverse to the position
   .FirstOrDefault();                 // Take the element


if(item!= null)
{
    Console.WriteLine(item.Key);
    // output - 3
}

Upvotes: 2

Tommy
Tommy

Reputation: 3124

int[] arr = new int[] { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 };

var lookup = arr.ToLookup(t => t);
var result = lookup.OrderByDescending(t => t.Count());

Console.WriteLine(result.ElementAt(1).Key);

Upvotes: 3

Related Questions