Рубрики

Найти потерянный элемент из дублированного массива

Учитывая, что два массива являются дубликатами друг друга, за исключением одного элемента, то есть один элемент из одного массива отсутствует, нам нужно найти этот отсутствующий элемент.

Примеры:

Input:  arr1[] = {1, 4, 5, 7, 9}
        arr2[] = {4, 5, 7, 9}
Output: 1
1 is missing from second array.

Input: arr1[] = {2, 3, 4, 5}
       arr2[] = {2, 3, 4, 5, 6}
Output: 6
6 is missing from first array.

Одно простое решение — перебирать массивы, проверять элемент за элементом и отмечать отсутствующий элемент при обнаружении несоответствия, но для этого решения требуется линейное время по размеру массива.

Другое эффективное решение основано на подходе бинарного поиска . Шаги алгоритма следующие:

  1. Начните бинарный поиск в большем массиве и получите середину как (lo + hi) / 2
  2. Если значение из обоих массивов одинаково, то отсутствующий элемент должен быть в правой части, поэтому установите lo как mid
  3. Иначе установите hi как mid, потому что отсутствующий элемент должен быть в левой части большего массива, если mid элементы не равны.
  4. Особый случай обрабатывается отдельно, как для одиночного элемента и массива нулевого элемента, сам элемент будет отсутствующим элементом.
    Если сам первый элемент не равен, то этот элемент будет отсутствующим элементом ./li>

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

C ++

// C ++ программа для поиска недостающего элемента из того же
// массивы (кроме одного отсутствующего элемента)
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска отсутствующего элемента на основе двоичного
// поисковый подход. arr1 [] имеет больший размер и
// N это размер. Предполагается, что arr1 [] и arr2 []
// быть в том же порядке.

int findMissingUtil(int arr1[], int arr2[], int N)

{

    // особый случай, только для элемента

    // отсутствует во втором массиве

    if (N == 1)

        return arr1[0];

  

    // особый случай, если отсутствует первый элемент

    if (arr1[0] != arr2[0])

        return arr1[0];

  

    // Инициализируем текущие угловые точки

    int lo = 0,  hi = N - 1;

  

    // цикл до lo <привет

    while (lo < hi)

    {

        int mid = (lo + hi) / 2;

  

        // Если элемент в середине индекса равен

        // затем перейдем к правильному подмассиву

        if (arr1[mid] == arr2[mid])

            lo = mid;

        else

            hi = mid;

  

        // если вот, привет становится смежным, перерыв

        if (lo == hi - 1)

            break;

    }

  

    // отсутствующий элемент будет с индексом hi

    // больший массив

    return arr1[hi];

}

  
// Эта функция в основном выполняет базовую проверку ошибок
// и вызывает findMissingUtil

void findMissing(int arr1[], int arr2[], int M, int N)

{

    if (N == M-1)

        cout << "Missing Element is "

        << findMissingUtil(arr1, arr2, M) << endl;

    else if (M == N-1)

        cout << "Missing Element is "

        << findMissingUtil(arr2, arr1, N) << endl;

    else

        cout << "Invalid Input";

}

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

int main()

{

    int arr1[] = {1, 4, 5, 7, 9};

    int arr2[] = {4, 5, 7, 9};

  

    int M = sizeof(arr1) / sizeof(int);

    int N = sizeof(arr2) / sizeof(int);

  

    findMissing(arr1, arr2, M, N);

  

    return 0;

}

Джава

// Java программа для поиска отсутствующего элемента
// из тех же массивов
// (кроме одного отсутствующего элемента)

  

import java.io.*;

class MissingNumber {

  

    / * Функция для поиска отсутствующего элемента на основе

     на подход бинарного поиска. arr1 [] имеет

     больший размер и N это размер it.arr1 [] и

     arr2 [] предполагается в том же порядке. * /

    int findMissingUtil(int arr1[], int arr2[],

                        int N)

    {

        // особый случай, только для элемента

        // который отсутствует во втором массиве

        if (N == 1)

            return arr1[0];

  

        // особый случай, для первого

        // элемент отсутствует

        if (arr1[0] != arr2[0])

            return arr1[0];

  

        // Инициализируем текущие угловые точки

        int lo = 0, hi = N - 1;

  

        // цикл до lo <привет

        while (lo < hi) {

            int mid = (lo + hi) / 2;

  

            // Если элемент в середине индекса

            // равный, затем перейти к правой подрешетке

            if (arr1[mid] == arr2[mid])

                lo = mid;

            else

                hi = mid;

  

            // если вот, привет становится

            // непрерывный, разрыв

            if (lo == hi - 1)

                break;

        }

  

        // отсутствующий элемент будет в hi

        // индекс большего массива

        return arr1[hi];

    }

  

    // Эта функция в основном делает основную ошибку

    // проверка и вызывает findMissingUtil

    void findMissing(int arr1[], int arr2[], 

                              int M, int N)

    {

        if (N == M - 1)

        System.out.println("Missing Element is "

        + findMissingUtil(arr1, arr2, M) + "\n");

        else if (M == N - 1)

        System.out.println("Missing Element is "

        + findMissingUtil(arr2, arr1, N) + "\n");

        else

        System.out.println("Invalid Input");

    }

  

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

    public static void main(String args[])

    {

        MissingNumber obj = new MissingNumber();

        int arr1[] = { 1, 4, 5, 7, 9 };

        int arr2[] = { 4, 5, 7, 9 };

        int M = arr1.length;

        int N = arr2.length;

        obj.findMissing(arr1, arr2, M, N);

    }

}

  
// Этот код предоставлен Аншикой Гоял.

python3

# Python3 программа для поиска пропавших без вести
# элемент из тех же массивов
# (кроме одного отсутствующего элемента)

  
# Функция для поиска отсутствующего элемента на основе
# о бинарном поиске. arr1 [] is
# большего размера, а N - его размер.
# arr1 [] и arr2 [] предполагаются
# быть в том же порядке.

def findMissingUtil(arr1, arr2, N):

  

    # особый случай, только для элемента

    # которого нет во втором массиве

    if N == 1:

        return arr1[0];

  

    # особый случай, для первого

    # элемент отсутствует

    if arr1[0] != arr2[0]:

        return arr1[0]

  

    # Инициализировать текущие угловые точки

    lo = 0

    hi = N - 1

      

    # цикл, пока не <привет

    while (lo < hi):

      

        mid = (lo + hi) / 2

  

        # Если элемент в середине индекса

        # равны, то перейдите к

        # правый подмассив

        if arr1[mid] == arr2[mid]:

            lo = mid

        else:

            hi = mid

  

        # если вот, привет становится

        # смежный, перерыв

        if lo == hi - 1:

            break

      

    # отсутствующий элемент будет в

    # привет индекс большего массива

    return arr1[hi]

  
# Эта функция в основном делает основной
# проверка ошибок и звонков
# findMissingUtil

def findMissing(arr1, arr2, M, N):

  

    if N == M-1:

        print("Missing Element is",

            findMissingUtil(arr1, arr2, M))

    elif M == N-1:

        print("Missing Element is",

            findMissingUtil(arr2, arr1, N))

    else:

        print("Invalid Input")

  
Код водителя

arr1 = [1, 4, 5, 7, 9]

arr2 = [4, 5, 7, 9]

M = len(arr1)

N = len(arr2)

findMissing(arr1, arr2, M, N)

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для поиска отсутствующего элемента из
// одинаковые массивы (кроме одного отсутствующего элемента)

using System;

  

class GFG {

  

    / * Функция для поиска отсутствующего элемента на основе

    на подход бинарного поиска. arr1 [] имеет

    больший размер и N это размер it.arr1 [] и

    arr2 [] предполагается в том же порядке. * /

    static int findMissingUtil(int []arr1, 

                            int []arr2, int N)

    {

          

        // особый случай, только для элемента

        // который отсутствует во втором массиве

        if (N == 1)

            return arr1[0];

  

        // особый случай, для первого

        // элемент отсутствует

        if (arr1[0] != arr2[0])

            return arr1[0];

  

        // Инициализируем текущие угловые точки

        int lo = 0, hi = N - 1;

  

        // цикл до lo <привет

        while (lo < hi) {

            int mid = (lo + hi) / 2;

  

            // Если элемент в середине индекса

            // равный, затем перейти к правой подрешетке

            if (arr1[mid] == arr2[mid])

                lo = mid;

            else

                hi = mid;

  

            // если вот, привет становится

            // непрерывный, разрыв

            if (lo == hi - 1)

                break;

        }

  

        // отсутствующий элемент будет в hi

        // индекс большего массива

        return arr1[hi];

    }

  

    // Эта функция в основном делает основную ошибку

    // проверка и вызывает findMissingUtil

    static void findMissing(int []arr1, int []arr2, 

                            int M, int N)

    {

        if (N == M - 1)

            Console.WriteLine("Missing Element is "

            + findMissingUtil(arr1, arr2, M) + "\n");

        else if (M == N - 1)

            Console.WriteLine("Missing Element is "

            + findMissingUtil(arr2, arr1, N) + "\n");

        else

            Console.WriteLine("Invalid Input");

    }

  

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

    public static void Main()

    {

        int []arr1 = { 1, 4, 5, 7, 9 };

        int []arr2 = { 4, 5, 7, 9 };

        int M = arr1.Length;

        int N = arr2.Length;

        findMissing(arr1, arr2, M, N);

    }

}

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

PHP

<?php
// PHP программа для поиска пропавшего
// элемент из тех же массивов
// (кроме одного отсутствующего элемента)

  
// Функция для поиска пропавшего
// элемент на основе двоичного
// поисковый подход. arr1 []
// имеет больший размер и
// N это размер. arr1 []
// и arr2 [] предполагаются
// быть в том же порядке.

function findMissingUtil($arr1, $arr2, $N)

{

      

    // особый случай, только для

    // элемент, который

    // отсутствует во втором массиве

    if ($N == 1)

        return $arr1[0];

  

    // особый случай, для первого

    // элемент отсутствует

    if ($arr1[0] != $arr2[0])

        return $arr1[0];

  

    // Инициализируем текущий

    // угловые точки

    $lo = 0;

    $hi = $N - 1;

  

    // цикл до lo <привет

    while ($lo < $hi)

    {

        $mid = ($lo + $hi) / 2;

  

        // Если элемент в середине индекса

        // равный, затем перейти к правой подрешетке

        if ($arr1[$mid] == $arr2[$mid])

            $lo = $mid;

        else

            $hi = $mid;

  

        // если вот, привет становится

        // непрерывный, разрыв

        if ($lo == $hi - 1)

            break;

    }

  

    // пропущенный элемент будет

    // в высоком индексе

    // больший массив

    return $arr1[$hi];

}

  
// Эта функция в основном
// выполняет базовую проверку ошибок
// и вызывает findMissingUtil

function findMissing($arr1, $arr2

                           $M, $N)

{

    if ($N == $M - 1)

        echo "Missing Element is "

             , findMissingUtil($arr1

                         $arr2, $M) ;

    else if ($M == $N - 1)

        echo "Missing Element is "

             , findMissingUtil($arr2

                           $arr1, $N);

    else

        echo "Invalid Input";

}

  

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

    $arr1 = array(1, 4, 5, 7, 9);

    $arr2 = array(4, 5, 7, 9);

    $M = count($arr1);

    $N = count($arr2);

    findMissing($arr1, $arr2, $M, $N);

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


Выход :

Missing Element is 1

Что делать, если входные массивы не в том же порядке?
В этом случае отсутствующий элемент — это просто XOR всех элементов обоих массивов. Спасибо Йоло Сонгу за предложение.

CPP

// C ++ программа для поиска недостающего элемента из одного массива
// такой, что в нем есть все элементы другого массива, кроме
// один. Элементы в двух массивах могут быть в любом порядке.
#include <bits/stdc++.h>

using namespace std;

  
// Эта функция в основном делает XOR всех элементов
// из arr1 [] и arr2 []

void findMissing(int arr1[], int arr2[], int M,

                 int N)

{

    if (M != N-1 && N != M-1)

    {

        cout << "Invalid Input";

        return;

    }

  

    // Делаем XOR всего элемента

    int res = 0;

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

       res = res^arr1[i];

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

       res = res^arr2[i];

  

    cout << "Missing element is " << res;

}

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

int main()

{

    int arr1[] = {4, 1, 5, 9, 7};

    int arr2[] = {7, 5, 9, 4};

  

    int M = sizeof(arr1) / sizeof(int);

    int N = sizeof(arr2) / sizeof(int);

  

    findMissing(arr1, arr2, M, N);

  

    return 0;

}

Джава

// Java программа для поиска отсутствующего элемента
// из одного массива так, чтобы у него было все
// элементы другого массива, кроме одного.
// Элементы в двух массивах могут быть в любом порядке.

  

import java.io.*;

class Missing {

      

    // Эта функция в основном делает XOR

    // все элементы arr1 [] и arr2 []

    void findMissing(int arr1[], int arr2[], 

                              int M, int N)

    {

        if (M != N - 1 && N != M - 1) {

        System.out.println("Invalid Input");

            return;

        }

  

        // Делаем XOR всего элемента

        int res = 0;

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

            res = res ^ arr1[i];

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

            res = res ^ arr2[i];

  

        System.out.println("Missing element is "

                                          + res);

    }

  

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

    public static void main(String args[])

    {

        Missing obj = new Missing();

        int arr1[] = { 4, 1, 5, 9, 7 };

        int arr2[] = { 7, 5, 9, 4 };

        int M = arr1.length;

        int N = arr2.length;

        obj.findMissing(arr1, arr2, M, N);

    }

}

  
// Этот код предоставлен Аншикой Гоял.

python3

# Python 3 программа для поиска
# отсутствует элемент из одного массива
# такой, что в нем есть все элементы
# другого массива кроме
# один. Элементы в двух массивах
# может быть в любом порядке.

  
# Эта функция в основном делает XOR всех элементов
# из arr1 [] и arr2 []

def findMissing(arr1,arr2, M, N):

    if (M != N-1 and N != M-1):

      

        print("Invalid Input")

        return

      

  

    # Делать XOR всего элемента

    res = 0

    for i in range(0,M):

        res = res^arr1[i];

    for i in range(0,N):

        res = res^arr2[i]

      

    print("Missing element is",res)

  
Код водителя

arr1 = [4, 1, 5, 9, 7]

arr2 = [7, 5, 9, 4]

M = len(arr1) 

N = len(arr2)

findMissing(arr1, arr2, M, N)

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

C #

// C # программа для поиска отсутствующего элемента
// из одного массива так, чтобы у него было все
// элементы другого массива, кроме одного.
// Элементы в двух массивах могут быть в
// Любой заказ.

using System;

class GFG {

      

    // Эта функция в основном делает XOR

    // все элементы arr1 [] и arr2 []

    static void findMissing(int []arr1,

                            int []arr2, 

                            int M, int N)

    {

        if (M != N - 1 && N != M - 1)

        {

            Console.WriteLine("Invalid Input");

            return;

        }

  

        // Делаем XOR всего элемента

        int res = 0;

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

            res = res ^ arr1[i];

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

            res = res ^ arr2[i];

  

        Console.WriteLine("Missing element is "

                                        + res);

    }

  

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

    public static void Main()

    {

      

        int []arr1 = {4, 1, 5, 9, 7};

        int []arr2 = {7, 5, 9, 4};

        int M = arr1.Length;

        int N = arr2.Length;

        findMissing(arr1, arr2, M, N);

    }

}

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

PHP

<?php
// PHP программа для поиска пропавшего
// элемент из одного массива
// такой, что в нем есть все элементы
// другого массива кроме
// один. Элементы в двух массивах
// может быть в любом порядке.

  
// Эта функция в основном делает
// XOR всех элементов
// из arr1 [] и arr2 []

function findMissing($arr1, $arr2

                           $M, $N)

{

    if ($M != $N - 1 && $N != $M - 1)

    {

        echo "Invalid Input";

        return;

    }

  

    // Делаем XOR всего элемента

    $res = 0;

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

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

          

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

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

    echo "Missing element is ", $res;

}

  

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

    $arr1 = array(4, 1, 5, 9, 7);

    $arr2 = array(7, 5, 9, 4);

    $M = sizeof($arr1);

    $N = sizeof($arr2);

  

    findMissing($arr1, $arr2, $M, $N);

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


Выход :

Missing Element is 1

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

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

Найти потерянный элемент из дублированного массива

0.00 (0%) 0 votes