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

Question

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

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

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 и менее раз

Answer 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() и возвращаем его.

Answer 2

Функция, работающая за линейное время за счет использования 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;
}

БЛОГ НА HUSL

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

Ответы (2 шт):