Самый частый номер в массиве

Question

У меня есть этот массив. Я написал функцию MostFreq, которая принимает массив целых чисел и возвращает 2 значения: более частое число в массиве и его частота проверяют этот код. Есть ли лучший способ сделать это?

static void Main()
{ 
    int [] M={4,5,6,4,4,3,5,3};
    int x;
    int f=MyMath.MostFreq(M,out x );
    console.WriteLine("the most Frequent Item = {0} with frequency = {1}",x,f);
}

=====

в классе Mymath

public static int MostFreq(int[] _M, out int x)
{
    //First I need to sort the array in ascending order
    int Max_Freq, No_Freq, i, k;
    Array.Sort(_M);                         
    k = _M[0];
    Max_Freq = 0; i = 0; x = 0;
    while (i < _M.Length)
    {
        //No_Freq= the frequency of the current number
        No_Freq = 0;
        //X here is the number which is appear in the array Frequently 
        while (k == _M[i])
        {
            No_Freq++;
            i++;
            if (i == _M.Length) 
                break;
        }
        if (No_Freq > Max_Freq)
        {
            //so it will be printed the same
            Max_Freq = No_Freq;
            x = k;
        }
        if (i < _M.Length) k = _M[i];
    }
    return (Max_Freq);
}

Answer 1

LINQ это вверх. Я знаю, что это в VB, но вы должны быть в состоянии преобразовать его в C #:

Dim i = From Numbers In ints _
            Group Numbers By Numbers Into Group _
            Aggregate feq In Group Into Count() _
            Select New With {.Number = Numbers, .Count = Count}

РЕДАКТИРОВАТЬ: теперь и в C #:

var i = from numbers in M
                group numbers by numbers into grouped
                select new { Number = grouped.Key, Freq = grouped.Count()};

Answer 2

Предполагая, что вы не можете использовать LINQ, я, вероятно, подхожу к алгоритму так:

• Создать словарь ключей / значений
• Итерируйте свой массив, добавьте ключ в словарь для каждого уникального элемента, увеличивайте значение каждый раз, когда этот элемент повторяется.
• Пройдите по словарным ключам и верните элемент с наибольшим значением.

Это не очень хорошее решение, но оно простое, ContainsKey - это поиск O (1), так что вы будете максимально не повторять свой массив дважды.

Answer 3

С точки зрения разработки программного обеспечения, я ожидаю, что функция MostFreq будет возвращать элемент с самой высокой частотой, а не саму частоту. Я бы выключил и вернул значения.

Answer 4

Вы можете исключить сортировку, которую вы делаете в начале, итерируя весь массив один раз, ведя счетчик того, сколько раз вы сталкиваетесь с каждым значением во временном массиве, а затем итерируя временный массив для наибольшего числа. Вы также можете сохранить как самую высокую частоту, так и самый частый элемент во всем.

Разные сорта имеют разную эффективность для разных типов данных, конечно, но это был бы наихудший случай всего из двух итераций.

Редактировать: Извинения за повтор ... 'Там не было, когда я начал:)

Answer 5

Совершено за 1 проход ....

public class PopularNumber
    {
        private Int32[] numbers = {5, 4, 3, 32, 6, 6, 3, 3, 2, 2, 31, 1, 32, 4, 3, 4, 5, 6};

        public PopularNumber()
        {
            Dictionary<Int32,Int32> bucket = new Dictionary<Int32,Int32>();
            Int32 maxInt = Int32.MinValue;
            Int32 maxCount = 0;
            Int32 count;

            foreach (var i in numbers)
            {
                if (bucket.TryGetValue(i, out count))
                {
                    count++;
                    bucket[i] = count;
                }
                else
                {
                    count = 1;
                    bucket.Add(i,count);
                }

                if (count >= maxCount)
                {
                    maxInt = i;
                    maxCount = count;
                }

            }

            Console.WriteLine("{0},{1}",maxCount, maxInt);

        }
    }

Answer 6

Вот пример, как вы могли бы сделать это без LINQ и без словарей и списков, просто два простых вложенных цикла:

public class MostFrequentNumber
{
    public static void Main()
    {
        int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        int counter = 0;
        int longestOccurance = 0;
        int mostFrequentNumber = 0;

        for (int i = 0; i < numbers.Length; i++)
        {
            counter = 0;

            for (int j = 0; j < numbers.Length; j++)
            {
                if (numbers[j] == numbers[i])
                {
                    counter++;
                }
            }

            if (counter > longestOccurance)
            {
                longestOccurance = counter;
                mostFrequentNumber = numbers[i];
            }
        }

        Console.WriteLine(mostFrequentNumber);
        //Console.WriteLine($"occured {longestOccurance} times");
    }
}

Вы получите значение наиболее часто встречающегося числа, и (прокомментировано) вы также можете получить номера вхождений. Я знаю, что у меня есть «using Linq;», это просто для преобразования исходной входной строки в массив int и избавления от пары строк и цикла синтаксического анализа. Алгоритм хорош даже без него, если заполнить массив «длинным» способом ...

Answer 7

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MostFrequentElement
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { 4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3, 1, 1, 7, 7, 7, 7, 7 };
            Array.Sort(array, (a, b) => a.CompareTo(b));
            int counter = 1;
            int temp=0 ;

            List<int> LOCE = new List<int>();
            foreach (int i in array)
            {
                counter = 1;
                foreach (int j in array)

{
                    if (array[j] == array[i])
                    {
                        counter++;
                    }
                    else {
                    counter=1;
                    }
                    if (counter == temp)
                    {
                        LOCE.Add(array[i]);
                    }
                    if (counter > temp)
                    {
                        LOCE.Clear();
                        LOCE.Add(array[i]);
                        temp = counter;

                    }
                }

            }
            foreach (var element in LOCE)
            {
                Console.Write(element + ",");
            }
            Console.WriteLine();
            Console.WriteLine("(" + temp + " times)");
            Console.Read();
        }
    }
}

Answer 8

int count = 1;
int currentIndex = 0;
for (int i = 1; i < A.Length; i++)
{
    if (A[i] == A[currentIndex])
        count++;
    else
        count--;
    if (count == 0)
    {
        currentIndex = i;
        count = 1;
    }
}

int mostFreq = A[currentIndex];