Рубрики

Программа на C / 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 ++ программа для поиска элемента
// встречаемся нечетное количество раз
#include <bits/stdc++.h>

using namespace std;

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

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;

}

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

int main()

{

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

                  4, 3, 5, 2, 4, 4, 2 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    // вызов функции

    cout << getOddOccurrence(arr, n);

  

    return 0;

}

Выход:

5

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

Лучшее решение — сделать битовую XOR для всех элементов. XOR всех элементов дает нам странный встречающийся элемент. Обратите внимание, что XOR двух элементов равно 0, если оба элемента одинаковы, а XOR числа x с 0 равно x.

Ниже приведена реализация вышеуказанного подхода.

C ++

// C ++ программа для поиска элемента
// встречаемся нечетное количество раз
#include <bits/stdc++.h>

using namespace std;

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

int getOddOccurrence(int ar[], int ar_size)

{

    int res = 0;

    for (int i = 0; i < ar_size; i++)

        res = res ^ ar[i];

  

    return res;

}

  
/ * Функция драйвера для проверки вышеуказанной функции * /

int main()

{

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

    int n = sizeof(ar) / sizeof(ar[0]);

  

    // вызов функции

    cout << getOddOccurrence(ar, n);

  

    return 0;

}

Выход:

5

С

// C программа для поиска элемента
// встречаемся нечетное количество раз
#include <stdio.h>

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

int getOddOccurrence(int ar[], int ar_size)

{

    int res = 0;

    for (int i = 0; i < ar_size; i++)

        res = res ^ ar[i];

  

    return res;

}

  
/ * Функция драйвера для проверки вышеуказанной функции * /

int main()

{

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

    int n = sizeof(ar) / sizeof(ar[0]);

  

    // вызов функции

    printf("%d", getOddOccurrence(ar, n));

    return 0;

}

Выход:

5

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

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

Программа на C / C ++ для поиска числа, встречающегося нечетное число раз

0.00 (0%) 0 votes