Рубрики

Java-программа, чтобы найти число, происходящее нечетное количество раз

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

Примеры :

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

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

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

class OddOccurrence {

  

    // функция для нахождения нечетного элемента

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

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

    {

        int i;

        for (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(String[] args)

    {

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

        int n = arr.length;

        System.out.println(getOddOccurrence(arr, n));

    }

}
// Этот код предоставлен Камалем Равалом

Выход:

5

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

Программа:

Джава

// Java-программа для поиска элемента, встречающегося нечетно
// количество раз

import java.io.*;

import java.util.HashMap;

  

class OddOccurrence {

    // функция для нахождения нечетного элемента

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

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

    {

        HashMap<Integer, Integer> hmap = new HashMap<>();

  

        // Помещаем все элементы в HashMap

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

            if (hmap.containsKey(arr[i])) {

                int val = hmap.get(arr[i]);

  

                // Если элемент массива уже присутствует

                // увеличить счетчик этого элемента.

                hmap.put(arr[i], val + 1);

            }

            else

  

                // если элемента массива нет, тогда ставим

                // элемент в HashMap и инициализация

                // количество до одного.

                hmap.put(arr[i], 1);

        }

  

        // Проверка нечетного вхождения каждого присутствующего элемента

        // в HashMap

        for (Integer a : hmap.keySet()) {

            if (hmap.get(a) % 2 != 0)

                return a;

        }

        return -1;

    }

  

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

    public static void main(String[] args)

    {

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

        int n = arr.length;

        System.out.println(getOddOccurrence(arr, n));

    }

}
// Этот код предоставлен Камалем Равалом

Выход:

5

Джава

// Java-программа для поиска элемента, встречающегося нечетное количество раз

  

class OddOccurance {

    int getOddOccurrence(int ar[], int ar_size)

    {

        int i;

        int res = 0;

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

            res = res ^ ar[i];

        }

        return res;

    }

  

    public static void main(String[] args)

    {

        OddOccurance occur = new OddOccurance();

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

        int n = ar.length;

        System.out.println(occur.getOddOccurrence(ar, n));

    }

}
// Этот код предоставлен Mayank Jaiswal

Выход:

5

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

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

Java-программа, чтобы найти число, происходящее нечетное количество раз

0.00 (0%) 0 votes