Убрать из массива элементы которые повторяются более чем два раза

Рейтинг: 0Ответов: 2Опубликовано: 04.03.2023

Задача: убрать из массива элементы которые повторяются более двух раз

Идея: берём каждый элемент и считаем сколько раз он повторяется и если больше двух раз то пропускаем этот элемент и берём следующий, иначе переписываем в выходной массив Код:

private static int[] removeElementsThatAppearMoreThanTwice(int[] input)
        {
            int[] filtered = new int[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                int countOfRepeat = 1;
                for (int j = 0; j < input.Length; j++)
                {
                    if (input[i] == input[j] && i != j)
                    {
                        countOfRepeat++;
                    }
                }
                if (countOfRepeat > 2)
                {
                    continue;
                }
                filtered[i] = input[i];
            }
            return filtered;
        }

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

c# алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

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

Вот как может выглядеть код:

private static int[] removeElementsThatAppearMoreThanTwice(int[] input)
{
    List<int> filtered = new List<int>();
    for (int i = 0; i < input.Length; i++)
    {
        int countOfRepeat = 0;
        for (int j = 0; j < input.Length; j++)
        {
            if (input[i] == input[j])
            {
                countOfRepeat++;
            }
        }
        if (countOfRepeat <= 2)
        {
            filtered.Add(input[i]);
        }
    }
    return filtered.ToArray();
}

В этой реализации мы используем List<int> filtered вместо int[] filtered для хранения элементов, которые появляются два раза и менее. Затем мы добавляем элементы, удовлетворяющие нашему условию (countOfRepeat <= 2), в filtered. Наконец, мы преобразуем filtered в массив с помощью ToArray() и возвращаем его.

▲ 3

Функция, работающая за линейное время за счет использования Dictionary:

using System;
using System.Collections.Generic;

IEnumerable<int> Filter(IEnumerable<int> input)
{
    const int limit = 2;

    var count = new Dictionary<int, int>();
    foreach (var x in input)
    {
        count[x] = count.GetValueOrDefault(x) + 1;
    }

    foreach (var x in input)
    {
        if (count[x] <= limit)
        {
            yield return x;
        }
    }
}

Console.WriteLine(string.Join(',', Filter(new[] { 1, 2, 3, 4 })));             // 1,2,3,4
Console.WriteLine(string.Join(',', Filter(new[] { 1, 2, 3, 4, 1, 3, 5, 7 }))); // 1,2,3,4,1,3,5,7
Console.WriteLine(string.Join(',', Filter(new[] { 1, 2, 1, 3, 1, 4, 1, 5 }))); // 2,3,4,5
Console.WriteLine(string.Join(',', Filter(new[] { 3, 2, 3, 3, 1, 2 })));       // 2,1,2

Если категорически не хотите использовать IEnumerable и Linq (а ToArray — это тоже Linq), то можно добавить подсчет количества элементов на выходе:

int[] Filter(int[] input)
{
    const int limit = 2;
    
    var count = new Dictionary<int, int>();
    foreach (var x in input)
    {
        count[x] = count.GetValueOrDefault(x) + 1;
    }
    
    var totalCount = 0;
    foreach (var x in input)
    {
        if (count[x] <= limit)
        {
            ++totalCount;
        }
    }
    
    var result = new int[totalCount];
    var index = -1;
    foreach (var x in input)
    {
        if (count[x] <= limit)
        {
            result[++index] = x;
        }
    }
    return result;
}

или

int[] Filter(int[] input)
{
    const int limit = 2;
    
    var count = new Dictionary<int, int>();
    var totalCount = 0;
    foreach (var x in input)
    {
        var currentCount = count[x] = count.GetValueOrDefault(x) + 1;
        if (currentCount <= limit)
        {
            ++totalCount;
        }
        else if (currentCount == limit + 1)
        {
            totalCount -= limit;
        }
    }
    
    var result = new int[totalCount];
    var index = -1;
    foreach (var x in input)
    {
        if (count[x] <= limit)
        {
            result[++index] = x;
        }
    }
    return result;
}