I'm stuck in this logic and I don't know how to solve it, I have the following question:

"Given a nums array of size n, return the majority element, that is, the element that appears the most times in your array."

And I have this code base:

`using System;
using System.Text.RegularExpressions;

public class Program
{
    public static void Main(String[] args)
    {
        int n = int.Parse(Console.ReadLine());
        
        int[] num = new int[n];

        
        for (int i = 0; i < n; i  )
        {
            num[i] = int.Parse(Console.ReadLine());
        }
        Console.WriteLine(MajorityElement(num)); 
    }




    public static int MajorityElement(int[] nums)
    {
        int major = nums[0];
        int count = 1;
        for (int i = 0; i < nums.Length; i  )
        {
            if ( )
            {
                major = nums[i];
                count  ;
            }
            else
            {
                if (major == nums[i])
                {
                    count  ;
                }
                else
                {
                    count--;
                }
            }
        }
        return major;
    }
}`

But I can't think of what the logic of the first IF would be.

How would that logic be in this question? And how would I solve it?

CodePudding user response：

A succinct but inefficient way to solve this is like so:

int major = nums.ToLookup(n => n).MaxBy(item => item.Count()).Key;

How does this work?

1. nums.ToLookup(n => n)

This uses Enumerable.ToLookup() to create a lookup table. The lookup table will contain one entry for each unique number in the array. Each entry will consist of a key (which is the number) and a list of all the numbers with the same value.

The n => n part selects the lookup key from each value. In this case they are the same, but usually it would be used to select some property from a class that you were creating a lookup for.

That is, given this list (the numbers can be in any order):

int[] nums = { 1, 2, 2, 3, 3, 3 };

Then the lookup table will have 3 elements (one for each unique number in the list) as follows:

[1] = {1}
[2] = {2, 2}
[3] = {3, 3, 3}

Note that the numbers in the square brackets are NOT indices - they are keys. They do not have to be integers; they could be strings, for example.

I think you will already be able to see how inefficient this really is! We shouldn't need to store a list of all the matching numbers just to obtain a count of them. Nevertheless, let's carry on with the explanation.

2. .MaxBy(item => item.Count())

This selects the maximum element of the lookup table according to each element's item.Count() which is the count of all the items for each element. In the example above, you can see that [1] has a count of 1, [2] has a count of 2 and [3] has a count of 3.

3. .Key

Once we've selected the maximum element in the lookup table according to the count, we just access the key for that element. Remember that the keys for the lookup tables are the integers that we've counted. The key of the element with the most items, therefore, is the number we're looking for.

A much more efficient approach: Use a Dictionary<Tkey, TValue>

We can use a dictionary to count the number of unique items. The dictionary keys will be the unique integer values in the list, and the dictionary value for each key will be the number of occurrences of that key.

var dict = new Dictionary<int, int>();

foreach (int value in nums)
{
    if (dict.ContainsKey(value))
          dict[value];
    else
        dict[value] = 1;
}

int major = dict.MaxBy(kvp => kvp.Value).Key;

This is much easier to understand. It goes through each number in the input and if it is not already in the dictionary, it adds a value of 1 to the dictionary. (This is of course the initial count.) If the number is already in the dictionary, it instead increments the value - i.e. it increments the count of occurrences of that number.

Finally the code selects the dictionary element with the highest value (i.e. highest repeat count) and selects the key for that value (which will be the number that was repeated that many times).