Рубрики

Найдите элемент, который появляется один раз

Дан массив, в котором каждый элемент встречается три раза, кроме одного, который встречается только один раз. Найдите элемент, который встречается один раз. Ожидаемая сложность по времени составляет O (n) и O (1) дополнительного пространства.
Примеры :

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2
In the given array all element appear three times except 2 which appears once.

Input: arr[] = {10, 20, 10, 30, 10, 30, 30}
Output: 20
In the given array all element appear three times except 20 which appears once.

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

Идея состоит в том, чтобы использовать побитовые операторы для решения, которое составляет O (n) времени и использует O (1) дополнительное пространство. Решение не так просто, как другие решения на основе XOR, потому что все элементы появляются здесь нечетное количество раз. Идея взята отсюда .

Запустите цикл для всех элементов в массиве. В конце каждой итерации поддерживайте следующие два значения.

единицы: биты, появившиеся 1-й, 4-й или 7-й раз … и т. д.

twos: биты, появившиеся во второй, пятый или восьмой раз и т. д.

Наконец, мы возвращаем значение «единицы»

Как сохранить значения единиц и двойок?
«none» и «twos» инициализируются как 0. Для каждого нового элемента в массиве найдите общие биты набора в новом элементе и предыдущее значение «ones». Эти общие биты на самом деле являются битами, которые должны быть добавлены к 'двойкам'. Так что делайте побитовое ИЛИ из общего набора битов с 'двойками'. 'twos' также получает некоторые дополнительные биты, которые появляются в третий раз. Эти дополнительные биты будут удалены позже.
Обновите «единицы», выполнив XOR для нового элемента с предыдущим значением «единицы». Там могут быть некоторые биты, которые появляются в 3-й раз. Эти дополнительные биты также удаляются позже.

Обе единицы и двойки содержат те дополнительные биты, которые появляются в 3-й раз. Удалите эти дополнительные биты, обнаружив общие биты в «единиц» и «двойки».

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

C ++

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

using namespace std;

  

int getSingle(int arr[], int n) 

    int ones = 0, twos = 0 ; 

  

    int common_bit_mask; 

  

    // Давайте рассмотрим пример {3, 3, 2, 3}, чтобы понять это

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

    

        / * Выражение "one & arr [i]" дает биты, которые

        там и в «единицы» и новый элемент из arr []. Мы

        добавить эти биты в 'двойки', используя побитовое ИЛИ

  

        Значение 'twos' будет установлено как 0, 3, 3 и 1 после 1-го,

        2-я, 3-я и 4-я итерации соответственно * /

        twos = twos | (ones & arr[i]); 

  

  

        / * XOR новые биты с предыдущими ', чтобы получить все биты

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

  

        Значение «единицы» будет установлено как 3, 0, 2 и 3 после 1-го,

        2-я, 3-я и 4-я итерации соответственно * /

        ones = ones ^ arr[i]; 

  

  

        / * Общие биты - это те биты, которые появляются в третий раз

        Таким образом, эти биты не должны присутствовать как в «единицах», так и в «двойках».

        common_bit_mask содержит все эти биты как 0, так что биты могут

        быть удаленным из "единицы" и "двойки"

  

        Значение 'common_bit_mask' будет установлено как 00, 00, 01 и 10

        после 1-й, 2-й, 3-й и 4-й итераций соответственно * /

        common_bit_mask = ~(ones & twos); 

  

  

        / * Удалить общие биты (биты, которые появляются в третий раз) из «единиц»

              

        Значение «единицы» будет установлено как 3, 0, 0 и 2 после 1-го,

        2-я, 3-я и 4-я итерации соответственно * /

        ones &= common_bit_mask; 

  

  

        / * Удалить общие биты (биты, которые появляются в третий раз) из 'двойки'

  

        Значение 'twos' будет установлено как 0, 3, 1 и 0 после 1-го,

        2-я, 3-я и 4-я итерации соответственно * /

        twos &= common_bit_mask; 

  

        // раскомментируем этот код, чтобы увидеть промежуточные значения

        // printf ("% d% d n", единицы, двойки);

    

  

    return ones; 

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

int main() 

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

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

    cout<<"The element with single occurrence is  "<<getSingle(arr, n); 

    return 0; 

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

С

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

  

int getSingle(int arr[], int n)

{

    int ones = 0, twos = 0 ;

  

    int common_bit_mask;

  

    // Давайте рассмотрим пример {3, 3, 2, 3}, чтобы понять это

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

    {

        / * Выражение "one & arr [i]" дает биты, которые

           там и в «единицы» и новый элемент из arr []. Мы

           добавить эти биты в 'двойки', используя побитовое ИЛИ

  

           Значение 'twos' будет установлено как 0, 3, 3 и 1 после 1-го,

           2-я, 3-я и 4-я итерации соответственно * /

        twos  = twos | (ones & arr[i]);

  

  

        / * XOR новые биты с предыдущими ', чтобы получить все биты

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

  

           Значение «единицы» будет установлено как 3, 0, 2 и 3 после 1-го,

           2-я, 3-я и 4-я итерации соответственно * /

        ones  = ones ^ arr[i];

  

  

        / * Общие биты - это те биты, которые появляются в третий раз

           Таким образом, эти биты не должны присутствовать как в «единицах», так и в «двойках».

           common_bit_mask содержит все эти биты как 0, так что биты могут

           быть удаленным из "единицы" и "двойки"

  

           Значение 'common_bit_mask' будет установлено как 00, 00, 01 и 10

           после 1-й, 2-й, 3-й и 4-й итераций соответственно * /

        common_bit_mask = ~(ones & twos);

  

  

        / * Удалить общие биты (биты, которые появляются в третий раз) из «единиц»

              

           Значение «единицы» будет установлено как 3, 0, 0 и 2 после 1-го,

           2-я, 3-я и 4-я итерации соответственно * /

        ones &= common_bit_mask;

  

  

        / * Удалить общие биты (биты, которые появляются в третий раз) из 'двойки'

  

           Значение 'twos' будет установлено как 0, 3, 1 и 0 после 1-го,

           2-я, 3-я и 4-я итерации соответственно * /

        twos &= common_bit_mask;

  

        // раскомментируем этот код, чтобы увидеть промежуточные значения

        // printf ("% d% d n", единицы, двойки);

    }

  

    return ones;

}

  

int main()

{

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

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

    printf("The element with single occurrence is %d ",

            getSingle(arr, n));

    return 0;

}

Джава

// Java-код для поиска элемента
// это происходит только один раз

  

class GFG

{

    // Метод поиска элемента, который встречается только один раз

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

    {

        int ones = 0, twos = 0;

        int common_bit_mask;

          

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

        {

            / * "one & arr [i]" дает биты, которые есть в

            оба 'единицы' и новый элемент из arr []. Мы

            добавьте эти биты в 'twos', используя побитовое ИЛИ * /

            twos = twos | (ones & arr[i]);

  

            / * "one & arr [i]" дает биты, которые

            там и в «единицы» и новый элемент из arr [].

            Мы добавляем эти биты в 'twos', используя побитовое ИЛИ * /

            ones = ones ^ arr[i];

  

            / * Общие биты - это те биты, которые появляются в третий раз

            Таким образом, эти биты не должны присутствовать как в «единицах», так и в «двойках».

            common_bit_mask содержит все эти биты как 0, так что биты могут

            быть удаленным из «единиц» и «двойок» * /

            common_bit_mask = ~(ones & twos);

                          

            / * Удалить общие биты (биты, которые появляются в третий раз) из «единиц» * /

            ones &= common_bit_mask;

                          

            / * Удалить общие биты (биты, которые появляются в третий раз) из 'двойки' * /

            twos &= common_bit_mask;

        }

        return ones;

    }

      

    // Метод драйвера

    public static void main(String args[])

    {

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

        int n = arr.length;

        System.out.println("The element with single occurrence is " + getSingle(arr, n));

    }

}
// Код предоставлен Rishab Jain

python3

# Python3 код для поиска элемента, который
# появляется один раз

  

def getSingle(arr, n):

    ones = 0

    twos = 0

      

    for i in range(n):

        # one & arr [i] "дает биты, которые

        # есть как в «единицах», так и в новых

        # элемент из arr []. Мы добавляем эти

        # битов в 'двойки' с использованием побитового ИЛИ

        twos = twos | (ones & arr[i])

          

        # one & arr [i] "дает биты, которые

        # есть как в «единицах», так и в новых

        # элемент из arr []. Мы добавляем эти

        # битов в 'двойки' с использованием побитового ИЛИ

        ones = ones ^ arr[i]

          

        # Общие биты - это те биты

        # которые появляются в третий раз. Так что эти

        # битов не должно быть в обоих

        # 'единицы' и 'двойки'. common_bit_mask

        # содержит все эти биты как 0, так

        # что биты могут быть удалены из

        # 'единицы' и 'двойки'

        common_bit_mask = ~(ones & twos)

          

        # Удалить общие биты (биты, которые

        # появляются в третий раз) из 'единицы'

        ones &= common_bit_mask

          

        # Удалить общие биты (биты, которые

        # появляются в третий раз) из 'двойки'

        twos &= common_bit_mask

    return ones

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

arr = [3, 3, 2, 3]

n = len(arr)

print("The element with single occurrence is ",

        getSingle(arr, n))

  
# Этот код предоставлен "Abhishek Sharma 44"

C #

// C # код для поиска элемента
// это происходит только один раз

using System;

class GFG

{

    // Метод для поиска элемента

    // это происходит только один раз

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

    {

        int ones = 0, twos = 0;

        int common_bit_mask;

          

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

        {

            // "one & arr [i]" дает биты

            // которые есть в обоих

            // и новый элемент из arr [].

            // Добавляем эти биты в 'twos'

            // используя побитовое ИЛИ

            twos = twos | (ones & arr[i]);

  

            // "one & arr [i]" дает биты

            // которые есть в обоих

            // и новый элемент из arr [].

            // Добавляем эти биты в 'twos'

            // используя побитовое ИЛИ

            ones = ones ^ arr[i];

  

            // Общими битами являются эти биты

            // которые появляются в третий раз

            // биты не должны быть в обоих

            // 'единицы' и 'двойки'. common_bit_mask

            // содержит все эти биты как 0,

            // чтобы биты можно было удалить

            // из 'единиц' и 'двойок'

            common_bit_mask = ~(ones & twos);

                          

            // Удалить общие биты (биты, которые

            // появляются в третий раз)

            ones &= common_bit_mask;

                          

            // Удалить общие биты (биты, которые

            // появляются в третий раз) из 'twos'

            twos &= common_bit_mask;

        }

        return ones;

    }

      

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

    public static void Main()

    {

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

        int n = arr.Length;

        Console.WriteLine("The element with single" +

            "occurrence is " + getSingle(arr, n));

    }

}

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

PHP

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

  

function getSingle($arr, $n)

{

    $ones = 0; $twos = 0 ;

  

    $common_bit_mask;

  

    // Давайте возьмем пример

    // {3, 3, 2, 3} чтобы понять это

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

    {

        / * Выражение "one & arr [i]"

        дает биты, которые есть в

        и «одни» и новый элемент из

        обр []. Мы добавляем эти биты в 'twos'

        используя побитовое ИЛИ

        Значение 'twos' будет установлено как 0,

        3, 3 и 1 после 1-го, 2-го, 3-го

        и 4-й итерации соответственно * /

        $twos = $twos | ($ones & $arr[$i]);

  

  

        / * XOR новые биты с предыдущими

        'единицы', чтобы все биты появлялись

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

  

        Значение «единицы» будет установлено как 3,

        0, 2 и 3 после 1-го, 2-го, 3-го и

        4-е итерации соответственно * /

        $ones = $ones ^ $arr[$i];

  

        / * Общими битами являются эти биты

        которые появляются в третий раз. Так что эти

        биты не должны быть в обоих

        'единицы' и 'двойки'. common_bit_mask

        содержит все эти биты как 0, так

        что биты могут быть удалены из

        'единицы' и 'двойки'

  

        Значение 'common_bit_mask' будет

        установить как 00, 00, 01 и 10 после 1-го,

        2-я, 3-я и 4-я итерации соответственно * /

        $common_bit_mask = ~($ones & $twos);

  

  

        / * Удалить общие биты (биты

        которые появляются в третий раз)

              

        Значение «единицы» будет установлено как 3,

        0, 0 и 2 после 1-го, 2-го, 3-го

        и 4-й итерации соответственно * /

        $ones &= $common_bit_mask;

  

  

        / * Удалить общие биты (биты

        которые появляются в третий раз) от 'двойки'

  

        Значение 'twos' будет установлено как 0, 3,

        1 и 0 после 1-го, 2-го, 3-го и 4-го

        итерации соответственно * /

        $twos &= $common_bit_mask;

  

        // раскомментируем этот код, чтобы увидеть

        // промежуточные значения

        // printf ("% d% d n", единицы, двойки);

    }

  

    return $ones;

}

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

$arr = array(3, 3, 2, 3);

$n = sizeof($arr);

echo "The element with single "

                "occurrence is "

             getSingle($arr, $n);

  
// Этот код предоставлен m_kit
?>


Выход :

The element with single occurrence is 2

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Далее следует другой O (n) временной сложности и O (1) метод дополнительного пространства, предложенный aj . Мы можем суммировать биты в одинаковых позициях для всех чисел и взять по модулю 3. Биты, для которых сумма не кратна 3, являются битами числа с одним вхождением.
Рассмотрим пример массива {5, 5, 5, 8}. 101, 101, 101, 1000
Сумма первых битов% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Сумма вторых битов% 3 = (0 + 0 + 0 + 0)% 0 = 0;
Сумма третьих битов% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Сумма четвертых битов% 3 = (1)% 3 = 1;
Следовательно, число, которое появляется один раз, равно 1000

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

C ++

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

using namespace std;

#define INT_SIZE 32 

  

int getSingle(int arr[], int n) 

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

    int result = 0; 

  

    int x, sum; 

  

    // перебирать каждый бит

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

    

          

    // Найти сумму установленных битов в i-й позиции во всех

    // элементы массива

    sum = 0; 

    x = (1 << i); 

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

    

        if (arr[j] & x) 

            sum++; 

    

  

    // Биты с суммой, не кратной 3, являются

    // биты элемента с одним вхождением.

    if (sum % 3) 

        result |= x; 

    

  

    return result; 

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

int main() 

    int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7}; 

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

    cout << "The element with single occurrence is " << getSingle(arr, n); 

    return 0; 

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

С

// C программа для поиска элемента
// это происходит только один раз
#include <stdio.h>
#define INT_SIZE 32

  

int getSingle(int arr[], int n)

{

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

    int result = 0;

  

    int x, sum;

  

    // перебирать каждый бит

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

    {

      // Найти сумму установленных битов в i-й позиции во всех

      // элементы массива

      sum = 0;

      x = (1 << i);

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

      {

          if (arr[j] & x)

            sum++;

      }

  

      // Биты с суммой, не кратной 3, являются

      // биты элемента с одним вхождением.

      if (sum % 3)

        result |= x;

    }

  

    return result;

}

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

int main()

{

    int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};

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

    printf("The element with single occurrence is %d ",

            getSingle(arr, n));

    return 0;

}

Джава

// Java-код для поиска элемента
// это происходит только один раз

  

class GFG

{

    static final int INT_SIZE = 32;

      

    // Метод поиска элемента, который встречается только один раз

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

    {

        int result = 0;

        int x, sum;

          

        // перебирать каждый бит

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

        {

            // Найти сумму установленных битов в i-й позиции во всех

            // элементы массива

            sum = 0;

            x = (1 << i);

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

            {

                if((arr[j] & x) == 0)

                sum++;

            }

            // Биты с суммой, не кратной 3, являются

            // биты элемента с одним вхождением.

            if ((sum % 3) == 0)

            result |= x;

        }

        return result;

    }

      

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};

        int n = arr.length;

        System.out.println("The element with single occurrence is " + getSingle(arr, n));

    }

      
}
// Код предоставлен Rishab Jain

Python 3

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

INT_SIZE = 32

  

def getSingle(arr, n) :

      

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

    result = 0

      

    # Перебирать каждый бит

    for i in range(0, INT_SIZE) :

          

        # Найти сумму установленных бит

        # в i-й позиции во всех

        # элементы массива

        sm = 0

        x = (1 << i)

        for j in range(0, n) :

            if (arr[j] & x) :

                sm = sm + 1

                  

        # Биты с суммой не

        # кратное 3, являются

        # бит элемента с

        # единичное вхождение.

        if (sm % 3) :

            result = result | x

      

    return result

      
# Драйверная программа

arr = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]

n = len(arr)

print("The element with single occurrence is "

      ,getSingle(arr, n))

  

  
# Этот код добавлен
# Никита Тивари.

C #

// C # код для поиска элемента
// это происходит только один раз

using System;

  

class GFG

{

    static int INT_SIZE = 32;

      

    // Метод для поиска элемента

    // это происходит только один раз

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

    {

        int result = 0;

        int x, sum;

          

        // перебирать каждый бит

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

        {

            // Находим сумму установленных битов в ih

            // позиция во всех элементах массива

            sum = 0;

            x = (1 << i);

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

            {

                if((arr[j] & x) == 0)

                sum++;

            }

              

            // Биты с суммой, не кратной

            // из 3, биты элемента

            // с единственным вхождением.

            if ((sum % 3) == 0)

            result |= x;

        }

        return result;

    }

      

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

    public static void Main()

    {

        int []arr = {12, 1, 12, 3, 12, 1, 

                      1, 2, 3, 2, 2, 3, 7};

        int n = arr.Length;

        Console.WriteLine("The element with single " +

                "occurrence is " + getSingle(arr, n));

    }

      
}

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

PHP

<?php
// PHP-код для поиска элемента
// это происходит только один раз

$INT_SIZE= 32;

  

function getSingle($arr, $n)

{

    global $INT_SIZE;

      

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

    $result = 0;

  

    $x; $sum;

  

    // перебирать каждый бит

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

    {

    // Находим сумму установленных битов в ih

    // позиция во всех элементах массива

    $sum = 0;

    $x = (1 << $i);

    for ($j = 0; $j < $n; $j++ )

    {

        if ($arr[$j] & $x)

            $sum++;

    }

  

    // Биты с суммой, не кратной

    // из 3, биты элемента

    // с единственным вхождением.

    if ($sum % 3)

        $result |= $x;

    }

  

    return $result;

}

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

$arr = array (12, 1, 12, 3, 12, 1, 

              1, 2, 3, 2, 2, 3, 7);

$n = sizeof($arr);

echo "The element with single occurrence is ",

                          getSingle($arr, $n);

          
// Этот код предоставлен ajit
?>


Выход :

The element with single occurrence is 7

Другой подход, предложенный Абхишеком Шармой 44 . Добавьте каждое число один раз и умножьте сумму на 3, мы получим трижды сумму каждого элемента массива. Сохраните это как thrice_sum. Вычтите сумму всего массива из суммы thrice_sum и разделите результат на 2. Получаемое число является требуемым числом (которое появляется в массиве один раз).

Массив []: [a, a, a, b, b, b, c, c, c, d]
Математическое уравнение = (3 * (a + b + c + d) — (a + a + a + b + b + b + c + c + c + d)) / 2

Проще говоря: (3 * (sum_of_array_without_duplicates) — (sum_of_array)) / 2

let arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Required no = ( 3*(sum_of_array_without_duplicates) - (sum_of_array) ) / 2
            = ( 3*(12 + 1 + 3 + 2) - (12 + 1 + 12 + 3 + 12 + 1 + 1 + 2 + 3 + 3))/2 
            = ( 3*     18          -      50) / 2
            = (54 - 50) / 2
            = 2 (required answer)

Как мы знаем, что набор не содержит дубликата элемента,
Но std :: set обычно реализуется как красно-черное дерево двоичного поиска. Вставка в эту структуру данных имеет наихудший случай сложности O (log (n)), поскольку дерево поддерживается сбалансированным. мы будем использовать набор здесь.

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

C ++

// C ++ программа для поиска элемента
// это происходит только один раз

  
#include <bits/stdc++.h>

using namespace std;

  
// функция, которая находит номер

int singleNumber(int a[],int n)

{

    unordered_set<int> s(a,a+n);

      

    int arr_sum=accumulate(a, a+n,0);// сумма массива

      

    int set_sum  = accumulate(s.begin(), s.end(),0);// сумма множества

      

    // Применяем формулу.

    return (3*set_sum-arr_sum)/2;

      
}

  
// функция драйвера

int main() {

   int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};

     

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

     

   cout<<"The element with single occurrence is "<<singleNumber(a,n);

}

  
// Этот код предоставлен Мохитом Кумаром 29 (IIIT Гвалиор)

Джава

// Java-программа для поиска элемента
// это происходит только один раз

import java.util.*;

  

class GFG

{

  

    // функция, которая находит номер

    static int singleNumber(int a[], int n)

    {

        HashSet<Integer> s = new HashSet<Integer>();

        for (int i : a)

        {

            s.add(i);

        }

  

        int arr_sum = 0;// сумма массива

        for (int i : a) 

        {

            arr_sum += i;

        }

  

        int set_sum = 0;// сумма множества

        for (int i : s) 

        {

            set_sum += i;

        }

  

        // Применяем формулу.

        return (3 * set_sum - arr_sum) / 2;

  

    }

  

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

    public static void main(String[] args)

    {

        int a[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};

        int n = a.length;

        System.out.println("The element with single "

                        "occurrence is " + singleNumber(a, n));

    }

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

python3

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

  
# функция, которая находит номер

def singleNumber(nums):

      

    # применение формулы.

    return (3 * sum(set(nums)) - sum(nums)) / 2

  
# функция драйвера.

a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]

print ("The element with single occurrence is "

                          int(singleNumber(a)))

C #

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

using System;

using System.Collections.Generic;

  

class GFG

{

  

    // функция, которая находит номер

    static int singleNumber(int []a, int n)

    {

        HashSet<int> s = new HashSet<int>();

        foreach (int i in a)

        {

            s.Add(i);

        }

  

        int arr_sum = 0;// сумма массива

        foreach (int i in a) 

        {

            arr_sum += i;

        }

  

        int set_sum = 0;// сумма множества

        foreach (int i in s) 

        {

            set_sum += i;

        }

  

        // Применяем формулу.

        return (3 * set_sum - arr_sum) / 2;

    }

  

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

    public static void Main(String[] args)

    {

        int []a = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};

        int n = a.Length;

        Console.WriteLine("The element with single "

                        "occurrence is " + singleNumber(a, n));

    }

}

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

PHP

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

  
// функция, которая находит номер

function singleNumber($a, $n)

{

    $s = array();

    for ($i = 0; $i < count($a); $i++)

        array_push($s, $a[$i]);

    $s = array_values(array_unique($s));

          

    $arr_sum = 0; // сумма массива

    for ($i = 0; $i < count($a); $i++)

    {

        $arr_sum += $a[$i];

    }

      

    $set_sum = 0; // сумма множества

    for ($i = 0; $i < count($s); $i++) 

    {

        $set_sum += $s[$i];

    }

  

    // Применяем формулу.

    return (int)(((3 * $set_sum) - 

                       $arr_sum) / 2);

}

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

$a = array(12, 1, 12, 3, 12, 1, 

           1, 2, 3, 2, 2, 3, 7);

$n = count($a);

print("The element with single occurrence is "

                          singleNumber($a, $n));

  
// Этот код предоставлен mits
?>


Выход :

The element with single occurrence is 7

Сложность времени: O (Nlog (N))
Вспомогательное пространство: O (N)

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

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

Найдите элемент, который появляется один раз

0.00 (0%) 0 votes