Рубрики

Найти число, встречающееся нечетное количество раз

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

Примеры :

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

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

Простое решение состоит в том, чтобы запустить два вложенных цикла. Внешний цикл выбирает все элементы один за другим, а внутренний цикл подсчитывает количество вхождений элемента, выбранного внешним циклом. Временная сложность этого решения составляет O (n 2 ).

Ниже приведена реализация подхода грубой силы:

C ++

// 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;

    }

Джава

// 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));

    }

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

python3

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

      
# функция, чтобы найти элемент, встречающийся нечетно
# количество раз

def getOddOccurrence(arr, arr_size):

      

    for i in range(0,arr_size):

        count = 0

        for j in range(0, arr_size):

            if arr[i] == arr[j]:

                count+=1

              

        if (count % 2 != 0):

            return arr[i]

          

    return -1

      

      
# код водителя

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

n = len(arr)

print(getOddOccurrence(arr, n))

  
# Этот код был добавлен
# Смита Динеш Семвал

C #

// 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

PHP

<?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). Но это требует дополнительного места для хеширования.

Программа:

C ++

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

using namespace std;

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

int getOddOccurrence(int arr[],int size)

{

      

    // Определение HashMap в C ++

    unordered_map<int, int> hash;

  

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

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

    {

        hash[arr[i]]++;

    }

    // перебираем HashMap для проверки элемента

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

    for(auto i : hash)

    {

        if(i.second % 2 != 0)

        {

            return i.first;

        }

    }

    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; 

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

Джава

// 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));

    }

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

python3

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

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

def getOddOccurrence(arr,size):

       

    # Определение HashMap в C ++

    Hash=dict()

   

    # Помещение всех элементов в HashMap

    for i in range(size):

        Hash[arr[i]]=Hash.get(arr[i],0) + 1;

      

    # Итерация по HashMap для проверки элемента

    # встречается нечетное количество раз и возвращает его

    for i in Hash:

  

        if(Hash[i]% 2 != 0):

            return i

    return -1

  

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

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

n = len(arr)

   
# Вызов функции

print(getOddOccurrence(arr, n)) 

  
# Этот код предоставлен Мохит Кумар

C #

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

using System;

using System.Collections.Generic; 

  

public class OddOccurrence 

{

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

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

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

    {

        Dictionary<int,int> hmap = new Dictionary<int,int>();

          

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

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

        {

            if(hmap.ContainsKey(arr[i]))

            {

                int val = hmap[arr[i]];

                          

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

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

                hmap.Remove(arr[i]);

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

            }

            else

                  

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

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

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

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

        }

  

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

        // в HashMap

        foreach(KeyValuePair<int, int> entry in hmap)

        {

            if(entry.Value % 2 != 0)

            {

                return entry.Key;

            }

        }

        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;

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

    }

}

  
// Этот код предоставлен Принчи Сингхом


Выход :

5

Лучшее решение — сделать битовую 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;

}

С

      
// 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;

}

Джава

// 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

питон

      
# Программа Python для поиска элемента, встречающегося нечетное количество раз

  

def getOddOccurrence(arr):

  

    # Инициализировать результат

    res = 0

      

    # Обойти массив

    for element in arr:

        # XOR с результатом

        res = res ^ element

  

    return res

  
# Тестовый массив

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

  

print "%d" % getOddOccurrence(arr)

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

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


Сложность времени:
O (n)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Найти число, встречающееся нечетное количество раз

0.00 (0%) 0 votes