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

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

Наткнулся на задачу.

Дан массив длины n. Необходимо найти максимальное число l (2 <= l <= n), чтобы для префикса массива n длины l выполнялось условие - из него возможно удалить один элемент так, чтобы каждое число встречалось одинаковое число раз

Пара примеров для наглядности сути задачи:

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

Пример 1

Ввод:

5

1 2 3 4 5

Вывод:

5

Пример 2

Ввод:

10

1 2 4 2 3 1 3 9 15 23

Вывод:

7

Изначально была мысль, что как будто надо с мапой это связать, но так ни к чему и не пришел...

Буду благодарен любым идеям, как это сделать оптимальным способом!

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

Ответы

▲ 0Принят

Можно трекать количество повторяюцихся значений и, например, если все значения повторяются 1 раз или, например, все значения повторяются Х раз и какое то другое только один раз, то сохраняем длину префикса.

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

int GetMaxPrefix(int[] data)
{
    var byNum = new Dictionary<int, int>();
    var byRepCount = new Dictionary<int, int>();

    var longest = 0;

    for (int i = 0; i < data.Length; i++)
    {
        var item = data[i];
        if (!byNum.ContainsKey(item)) byNum[item] = 1;
        else byNum[item]++;

        if (!byRepCount.ContainsKey(byNum[item])) byRepCount[byNum[item]] = 0;
        if (!byRepCount.ContainsKey(byNum[item] - 1)) byRepCount[byNum[item] - 1] = 0;

        byRepCount[byNum[item]]++;
        byRepCount[byNum[item] - 1]--;
        if (byRepCount[byNum[item] - 1] <= 0) byRepCount.Remove(byNum[item] - 1);

        if (byRepCount.Count <= 2)
        {
            if (byRepCount.Count == 1 && byRepCount.ContainsKey(1)) longest = i;
            if (byRepCount.Count == 2)
            {
                if (byRepCount.Values.Any(z => z == 1)) longest = i;
            }
        }

    }

    return longest + 1;
}

Проверка

Console.WriteLine(GetMaxPrefix(new [] {1, 2, 3, 4, 5}));
Console.WriteLine(GetMaxPrefix(new [] {1, 2, 4, 2, 3, 1, 3, 9, 15, 23}));

Вывод

5
7