Рубрики

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

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

Примеры :

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

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

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

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

function getOddOccurrence(&$arr, $arr_size)

{

    $count = 0;

    for ($i = 0; 

         $i < $arr_size; $i++) 

    {

          

        for ($j = 0;

             $j < $arr_size; $j++)

        {

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

                $count++;

        }

        if ($count % 2 != 0)

            return $arr[$i];

    }

    return -1;

}

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

$arr = array(2, 3, 5, 4, 5, 2, 

             4, 3, 5, 2, 4, 4, 2);

$n = sizeof($arr);

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

echo(getOddOccurrence($arr, $n));

  
// Этот код добавлен
// от Shivi_Aggarwal
?>

Выход:

5

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

Программа:

PHP

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

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

function getOddOccurrence(&$ar, $ar_size)

{

    $res = 0; 

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

        $res = $res ^ $ar[$i];

      

    return $res;

}

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

$ar = array(2, 3, 5, 4, 5, 2,

            4, 3, 5, 2, 4, 4, 2);

$n = sizeof($ar);

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

echo(getOddOccurrence($ar, $n));

      
// Этот код добавлен
// от Shivi_Aggarwal
?>

Выход:

5

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

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

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

0.00 (0%) 0 votes