Найти уникальное число

Question

Найти уникальное число

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

Задача:

There is an array with some numbers. All numbers are equal except for one. Try to find it!

Есть массив с несколькими числами. Все числа равны кроме одного. Попробуйте найти его(перевод авторский за качество не ручаюсь, но вроде ничего сложного)

Моя идея:

Идём по массиву и кидаем каждое число в словарь при этом если число уже встречалось то увеличиваем кол-во раз сколько оно нам встретилось и вот с этим у меня проблема, читал на метаните про dictionary и там нет, как увеличить поле значение у ключа, а если не встречалось то кидаем в словарь и поле значение устанавливаем в единицу

План В:

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

Проблема:

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

Мой код :

private static int GetUnique(IEnumerable<int> numbers)
        {
            int unique = 0;
            var dict = new Dictionary<int, int>();
            foreach (var number in numbers)
            {
                if (dict.ContainsKey(number))
                {
                    dict[number] += 1;
                }
                else 
                { 
                    dict.Add(number, 1);
                }
            }
            foreach (var number in dict)
            {
                if (number.Value == 1)
                { 
                    unique = number.Key;
                }
            }
            return unique;
    }

c# структуры-данных

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Как-то так получается

using var enumerator = numbers.GetEnumerator();
enumerator.MoveNext();
int number1 = enumerator.Current; // берём первое число из последовательности
enumerator.MoveNext();
int number2 = enumerator.Current; // берём второе
if (number1 == number2) // если они равны
{
    while (enumerator.MoveNext()) // ищем дальше, пока не найдём
    {
        int number = enumerator.Current;
        if (number != number1)
            return number;
    }
    throw new ArgumentException("Все числа в последовательности равны");
}
else
{
    enumerator.MoveNext();
    if (enumerator.Current == number1) // иначе берем третье число и сравниваем с первым
        return number2;
    else
        return number1;
}

Со словарём тоже можно решить с одной оговоркой, если у вас в словарь добавлено уже 2 числа, а у одного из них количество больше 1, то нет смысла искать дальше, верно? А вы безусловно по всей коллекции проходили.

Answer 2

▲ 0

Если одинаковые числа записаны попарно и уникальное число только одно, то нужно проXOR-ить все значения массива, и нужное уникальное число само всплывет. Дело в том, что XOR любого числа на само себя дает ноль.

public int FindUnique(int[] numbers)
{
    int result = 0;

    for (int i = 0; i < numbers.Length; i++)
    {
        // Применяем операцию XOR ко всем элементам массива
        result ^= numbers[i];
    }

    return result;
}

Проверяем:

int[] numbers = { 2, 3, 2, 1, 3 };
Console.WriteLine(FindUnique(numbers)); // выводит "1"

Найти уникальное число

Ответы