Рубрики

Программа на C # для нахождения числа, происходящего нечетное количество раз

Дан массив натуральных чисел. Все числа встречаются четное число раз, кроме одного числа, которое встречается нечетное количество раз. Найдите число в O (n) времени и постоянном пространстве.

Примеры :

Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5

// C # программа для поиска элемента
// встречаемся нечетное количество раз

using System;

  

class GFG {

    // Функция для поиска элемента

    // встречаемся нечетное количество раз

    static int getOddOccurrence(int[] arr, int arr_size)

    {

        for (int i = 0; i < arr_size; i++) {

            int count = 0;

  

            for (int j = 0; j < arr_size; j++) {

                if (arr[i] == arr[j])

                    count++;

            }

            if (count % 2 != 0)

                return arr[i];

        }

        return -1;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };

        int n = arr.Length;

        Console.Write(getOddOccurrence(arr, n));

    }

}

  
// Этот код предоставлен Sam007

Выход:

5

Лучшее решение — использовать хеширование. Используйте элементы массива в качестве ключа и их количество в качестве значения. Создайте пустую хеш-таблицу. Один за другим пересекают заданные элементы массива и сохраняют счетчики. Временная сложность этого решения составляет O (n). Но это требует дополнительного места для хеширования.

Программа:

C #

// C # программа для поиска элемента
// встречаемся нечетное количество раз

using System;

  

class GFG {

    // Функция для поиска элемента

    // встречаемся нечетное количество раз

    static int getOddOccurrence(int[] arr, int arr_size)

    {

        int res = 0;

        for (int i = 0; i < arr_size; i++) {

            res = res ^ arr[i];

        }

        return res;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 };

        int n = arr.Length;

        Console.Write(getOddOccurrence(arr, n));

    }

}

  
// Этот код предоставлен Sam007

Выход:

5

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

Рекомендуемые посты:

Программа на C # для нахождения числа, происходящего нечетное количество раз

0.00 (0%) 0 votes