Сортировка массива по частоте элементов в C# - PullRequest
Новая
       8

Сортировка массива по частоте элементов в C#

2 голосов
/ 11 января 2020

Вот что у меня есть 

int[] numbers = { 3,5,4,3,8,8,5,3,2,1,9,5 };
int[] n = new int[12];
int[] k;

foreach (int number in numbers)
{
    n[number]++;
}
Array.Sort(n);
Array.Reverse(n);

foreach (int value in n)
{
    Console.WriteLine(value);
}

Я знаю, что мне не хватает той части, где я сортирую частоту элементов после того, как я их посчитал, и я просто не могу разобраться с этим. Буду признателен за помощь, спасибо!

Ответы [ 3 ]

1 голос
/ 11 января 2020

В чем проблема с вашим решением?

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

Например, если экземпляр этого массива - это [8,2,1,7,6]. Когда вы вызываете метод Sort для этого массива, это приведет к тому, что массив будет отсортирован, и порядок элементов массива будет таким [1,2,7,6,8]. Перед вызовом sort первый элемент массива указывал, что число 0 (индекс первого элемента равен 0) было найдено 8 раз в нашем numbers. После сортировки первый элемент равен 1, что означает, что частота 0 равна 1, что, по-видимому, неверно.

Если вы хотите сохранить свой путь, то вы можете попробовать что-то вроде этого: 

int[] numbers = {  1,2,2,9,1,2,5,5,5,5,2 };
int[] frequencies = new int[12];
int k = 3;

foreach (int number in numbers)
{
    frequencies[number]++;
}

var mostFrequentNumbers = frequencies.Select((frequency, index) => new 
                                            { 
                                                Number = index,
                                                Frequency = frequency
                                            })
                                      .OrderByDescending(item => item.Frequency)
                                      .Select(item => item.Number)
                                      .Take(k);

foreach (int mostFrequentNumber in mostFrequentNumbers)
{
   Console.WriteLine(mostFrequentNumber);
}

Есть ли другие подходы?

Самый простой способ сделать это - использовать структуру данных, такую ​​как Словарь, в которой вы будете хранить в качестве ключей числа и соответствующие значения соответствующих частот.

Затем вы можете упорядочить по убыванию значений указанную выше структуру данных и сохранить k наиболее часто встречающихся чисел. 

int[] numbers = { 1,2,2,9,1,2,5,5,5,5,2 };
int k = 3;

Dictionary<int, int> numberFrequencies = new Dictionary<int, int>();

foreach (int number in numbers)
{
    if(numberFrequencies.ContainsKey(number))
    {
        numberFrequencies[number] += 1;
    }
    else
    {
            numberFrequencies.Add(number, 1);
    }
}


var mostFrequentNumbers = numberFrequencies.OrderByDescending(numberFrequency => numberFrequency.Value)
                                           .Take(k)
                                           .Select(numberFrequency => numberFrequency.Key);


foreach (int mostFrequentNumber in mostFrequentNumbers)
{
    Console.WriteLine(mostFrequentNumber);
}

Этого же можно добиться, только используя LINQ: 

int[] numbers = { 1,2,2,9,1,2,5,5,5,5,2 };
int k = 3;

var mostFrequentNumbers = numbers.GroupBy(number => number)
                                 .ToDictionary(gr => gr.Key, gr => gr.Count())
                                 .OrderByDescending(keyValue => keyValue.Value)
                                 .Take(k)
                                 .Select(numberFrequency => numberFrequency.Key);


foreach (int mostFrequentNumber in mostFrequentNumbers)
{
    Console.WriteLine(mostFrequentNumber);
}
0 голосов
/ 11 января 2020

Быть очень кратким: 

var frequents = numbers.GroupBy(t => t)
    .Where(grp => grp.Count() > 1)
    .Select(t => t.Key)
    .OrderByDescending(t => t)
    .Take(k)
    .ToList();
0 голосов
/ 11 января 2020

Вы можете просто использовать расширения Linq: 

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

...

private static IEnumerable<int> Solve(int[] numbers, int k) {
    return numbers
        .GroupBy(x => x)
        .OrderByDescending(g => g.Count())
        .Select(g => g.Key)
        .Take(k);
}

Тогда вы можете позвонить: 

var numbers = new []{1,2,2,9,1,2,5,5,5,5,2};
var k = 3;
var result = Solve(numbers, k);
foreach (int n in result)
    Console.WriteLine(n);
...