Рубрики

Найти повторяющееся и пропавшее | Добавлено 3 новых метода

Дан несортированный массив размером n. Элементы массива находятся в диапазоне от 1 до n. Одно число из набора {1, 2,… n} отсутствует, и одно число встречается в массиве дважды. Найдите эти два числа.

Примеры:

 
Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 
2 is missing and 3 occurs twice 

Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1

Ниже приведены различные методы решения проблем:

  • Способ 1 (использовать сортировку)

    Подходить:

    1. Сортировать входной массив.
    2. Пройдите через массив и проверьте, нет ли и повторяется.

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

    Спасибо LoneShadow за предложение этого метода.

  • Способ 2 (использовать массив count)

    Подходить:

    1. Создайте временный массив temp [] размера n со всеми начальными значениями, равными 0.
    2. Пройдите по входному массиву arr [] и выполните следующее для каждого arr [i]
      • if (temp [arr [i]] == 0) temp [arr [i]] = 1;
      • if (temp [arr [i]] == 1) вывести «arr [i]» // повторение
    3. Пройдите temp [] и выведите элемент массива со значением 0 (это отсутствующий элемент)

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

  • Способ 3 (использовать элементы в качестве индекса и отмечать посещенные места)

    Подходить:
    Пройдите через массив. При обходе используйте абсолютное значение каждого элемента в качестве индекса и сделайте значение этого индекса отрицательным, чтобы отметить его посещение. Если что-то уже помечено как отрицательное, то это повторяющийся элемент. Чтобы найти недостающие, снова обойдите массив и найдите положительное значение.

    C ++

    // C ++ программа для поиска повторяющихся
    // и недостающие элементы

      
    #include <bits/stdc++.h>

    using namespace std;

      

    void printTwoElements(int arr[], int size)

    {

        int i;

        cout << " The repeating element is ";

      

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

            if (arr[abs(arr[i]) - 1] > 0)

                arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];

            else

                cout << abs(arr[i]) << "\n";

        }

      

        cout << "and the missing element is ";

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

            if (arr[i] > 0)

                cout << (i + 1);

        }

    }

      
    / * Код водителя * /

    int main()

    {

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

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

        printTwoElements(arr, n);

    }

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

    С

    // C программа для поиска повторяющихся
    // и недостающие элементы

      
    #include <stdio.h>
    #include <stdlib.h>

      

    void printTwoElements(int arr[], int size)

    {

        int i;

        printf("\n The repeating element is");

      

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

            if (arr[abs(arr[i]) - 1] > 0)

                arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];

            else

                printf(" %d ", abs(arr[i]));

        }

      

        printf("\nand the missing element is ");

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

            if (arr[i] > 0)

                printf("%d", i + 1);

        }

    }

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

    int main()

    {

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

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

        printTwoElements(arr, n);

        return 0;

    }

    Джава

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

      

    import java.io.*;

      

    class GFG {

      

        static void printTwoElements(int arr[], int size)

        {

            int i;

            System.out.print("The repeating element is ");

      

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

                int abs_val = Math.abs(arr[i]);

                if (arr[abs_val - 1] > 0)

                    arr[abs_val - 1] = -arr[abs_val - 1];

                else

                    System.out.println(abs_val);

            }

      

            System.out.print("And the missing element is ");

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

                if (arr[i] > 0)

                    System.out.println(i + 1);

            }

        }

      

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

        public static void main(String[] args)

        {

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

            int n = arr.length;

            printTwoElements(arr, n);

        }

    }

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

    python3

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

      

    def printTwoElements( arr, size):

        for i in range(size):

            if arr[abs(arr[i])-1] > 0:

                arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]

            else:

                print("The repeating element is", abs(arr[i]))

                  

        for i in range(size):

            if arr[i]>0:

                print("and the missing element is", i + 1)

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

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

    n = len(arr)

    printTwoElements(arr, n)

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

    C #

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

      

    using System;

      

    class GFG {

        static void printTwoElements(int[] arr, int size)

        {

            int i;

            Console.Write("The repeating element is ");

      

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

                int abs_val = Math.Abs(arr[i]);

                if (arr[abs_val - 1] > 0)

                    arr[abs_val - 1] = -arr[abs_val - 1];

                else

                    Console.WriteLine(abs_val);

            }

      

            Console.Write("And the missing element is ");

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

                if (arr[i] > 0)

                    Console.WriteLine(i + 1);

            }

        }

      

        // Драйвер программы

        public static void Main()

        {

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

            int n = arr.Length;

            printTwoElements(arr, n);

        }

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

    PHP

    <?php
    // PHP-программа для поиска повторяющихся
    // и недостающие элементы

      

    function printTwoElements($arr, $size)

    {

        $i;

        echo "The repeating element is", " ";

      

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

        {

            if($arr[abs($arr[$i]) - 1] > 0)

                $arr[abs($arr[$i]) - 1] = 

                - $arr[abs($arr[$i]) - 1];

            else

                echo ( abs($arr[$i]));

        }

      

        echo "\nand the missing element is ";

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

        {

            if($arr[$i] > 0)

                echo($i + 1);

        }

    }

          

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

        $arr = array(7, 3, 4, 5, 5, 6, 2);

        $n = count($arr);

        printTwoElements($arr, $n);

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

    Выход:

    The repeating element is 5
    and the missing element is 1
    

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

    Спасибо Манишу Мишре за предложение этого метода.

  • Метод 4 (сделать два уравнения)

    Подходить:

    1. Пусть x будет отсутствующим и y будет повторяющимся элементом.
    2. Получить сумму всех чисел, используя формулу S = n (n + 1) / 2 — x + y
    3. Получить произведение всех чисел, используя формулу P = 1 * 2 * 3 *… * n * y / x
    4. Вышеупомянутые два шага дают нам два уравнения, мы можем решить уравнения и получить значения x и y.

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

    Спасибо исчезнувшему за предложение этого решения.

    Примечание. Этот метод может вызвать арифметическое переполнение, поскольку мы вычисляем произведение и сумму всех элементов массива.

  • Метод 5 (Используйте XOR)

    Подходить:

    1. Пусть x и y будут желаемыми выходными элементами.
    2. Рассчитать XOR всех элементов массива.

      xor1 = arr[0]^arr[1]^arr[2]…..arr[n-1]

    3. XOR результат со всеми числами от 1 до n

      xor1 = xor1^1^2^…..^n

    4. В результате xor1 все элементы обнуляют друг друга, кроме x и y. Все биты, которые установлены в xor1, будут установлены в x или y. Таким образом, если мы возьмем любой установленный бит (мы выбрали самый правый установленный бит в коде) xor1 и разделим элементы массива на два набора — один набор элементов с одинаковым набором битов, а другой набор с одинаковым битом не установлен. Таким образом, мы получим x в одном наборе и y в другом наборе. Теперь, если мы сделаем XOR для всех элементов в первом наборе, мы получим x, и, делая то же самое в другом наборе, мы получим y ..
    5. Ниже приведена реализация вышеуказанного подхода:

      C ++

      // C ++ программа для поиска повторяющихся
      // и недостающие элементы

        
      #include <bits/stdc++.h>

      using namespace std;

        
      / * Выход этой функции хранится в
      * х и * у * /

      void getTwoElements(int arr[], int n,

                          int* x, int* y)

      {

          / * Будет содержать xor всех элементов

          и цифры от 1 до n * /

          int xor1;

        

          / * Будет иметь только один установленный бит xor1 * /

          int set_bit_no;

        

          int i;

          *x = 0;

          *y = 0;

        

          xor1 = arr[0];

        

          / * Получить xor всех элементов массива * /

          for (i = 1; i < n; i++)

              xor1 = xor1 ^ arr[i];

        

          / * XOR предыдущий результат с числами

          от 1 до n * /

          for (i = 1; i <= n; i++)

              xor1 = xor1 ^ i;

        

          / * Получить самый правый установленный бит в set_bit_no * /

          set_bit_no = xor1 & ~(xor1 - 1);

        

          / * Теперь разделим элементы на две части

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

          бит xor1 с битом в то же

          положение в каждом элементе. Также,

          получить XOR из двух наборов. Два

          XOR - это выходные элементы.

          Следующие два для петель

          служить цели * /

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

              if (arr[i] & set_bit_no)

                  / * arr [i] принадлежит первому набору * /

                  *x = *x ^ arr[i];

        

              else

                  / * arr [i] принадлежит второму набору * /

                  *y = *y ^ arr[i];

          }

          for (i = 1; i <= n; i++) {

              if (i & set_bit_no)

                  / * я принадлежу к первому набору * /

                  *x = *x ^ i;

        

              else

                  / * я принадлежу ко второму набору * /

                  *y = *y ^ i;

          }

        

          / * * x и * y удерживают желаемое

              выходные элементы * /

      }

        
      / * Код водителя * /

      int main()

      {

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

          int* x = (int*)malloc(sizeof(int));

          int* y = (int*)malloc(sizeof(int));

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

        

          getTwoElements(arr, n, x, y);

          cout << " The missing element is " << *x << " and the repeating"

               << " number is " << *y;

          getchar();

      }

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

      С

      // C программа для поиска повторяющихся
      // и недостающие элементы

        
      #include <stdio.h>
      #include <stdlib.h>

        
      / * Выход этой функции хранится в

         * х и * у * /

      void getTwoElements(int arr[], int n, int* x, int* y)

      {

          / * Будет содержать xor всех элементов и чисел

             от 1 до n * /

          int xor1;

        

          / * Будет иметь только один установленный бит xor1 * /

          int set_bit_no;

        

          int i;

          *x = 0;

          *y = 0;

        

          xor1 = arr[0];

        

          / * Получить xor всех элементов массива * /

          for (i = 1; i < n; i++)

              xor1 = xor1 ^ arr[i];

        

          / * XOR предыдущий результат с числами

             от 1 до n * /

          for (i = 1; i <= n; i++)

              xor1 = xor1 ^ i;

        

          / * Получить самый правый установленный бит в set_bit_no * /

          set_bit_no = xor1 & ~(xor1 - 1);

        

          / * Теперь разделите элементы на два набора, сравнивая

          крайний правый бит xor1 с битом

          положение в каждом элементе. Кроме того, получите XOR двух

          наборы. Два XOR являются выходными элементами.

          следующие две петли служат цели * /

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

              if (arr[i] & set_bit_no)

                  / * arr [i] принадлежит первому набору * /

                  *x = *x ^ arr[i];

        

              else

                  / * arr [i] принадлежит второму набору * /

                  *y = *y ^ arr[i];

          }

          for (i = 1; i <= n; i++) {

              if (i & set_bit_no)

                  / * я принадлежу к первому набору * /

                  *x = *x ^ i;

        

              else

                  / * я принадлежу ко второму набору * /

                  *y = *y ^ i;

          }

        

          / * * x и * y содержат нужные выходные элементы * /

      }

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

      int main()

      {

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

          int* x = (int*)malloc(sizeof(int));

          int* y = (int*)malloc(sizeof(int));

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

        

          getTwoElements(arr, n, x, y);

          printf(" The missing element is %d"

                 " and the repeating number"

                 " is %d",

                 *x, *y);

          getchar();

      }

      Джава

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

        

      import java.io.*;

        

      class GFG {

          static int x, y;

        

          static void getTwoElements(int arr[], int n)

          {

              / * Будет содержать xor всех элементов

             и цифры от 1 до n * /

              int xor1;

        

              / * Будет иметь только один установленный бит xor1 * /

              int set_bit_no;

        

              int i;

              x = 0;

              y = 0;

        

              xor1 = arr[0];

        

              / * Получить xor всех элементов массива * /

              for (i = 1; i < n; i++)

                  xor1 = xor1 ^ arr[i];

        

              / * XOR предыдущий результат с числами из

             От 1 до n * /

              for (i = 1; i <= n; i++)

                  xor1 = xor1 ^ i;

        

              / * Получить самый правый установленный бит в set_bit_no * /

              set_bit_no = xor1 & ~(xor1 - 1);

        

              / * Теперь разделите элементы на два набора, сравнивая

          крайний правый бит xor1 с одним битом

          положение в каждом элементе. Кроме того, получите XOR двух

          наборы. Два XOR являются выходными элементами.

          следующие две петли служат цели * /

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

                  if ((arr[i] & set_bit_no) != 0)

                      / * arr [i] принадлежит первому набору * /

                      x = x ^ arr[i];

        

                  else

                      / * arr [i] принадлежит второму набору * /

                      y = y ^ arr[i];

              }

              for (i = 1; i <= n; i++) {

                  if ((i & set_bit_no) != 0)

                      / * я принадлежу к первому набору * /

                      x = x ^ i;

        

                  else

                      / * я принадлежу ко второму набору * /

                      y = y ^ i;

              }

        

              / * * x и * y содержат нужные выходные элементы * /

          }

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

          public static void main(String[] args)

          {

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

        

              int n = arr.length;

              getTwoElements(arr, n);

              System.out.println(" The missing element is  "

                                 + x + "and the "

                                 + "repeating number is "

                                 + y);

          }

      }

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

      C #

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

        

      using System;

        

      class GFG {

          static int x, y;

        

          static void getTwoElements(int[] arr, int n)

          {

              / * Будет содержать xor всех элементов

              и цифры от 1 до n * /

              int xor1;

        

              / * Будет иметь только один установленный бит xor1 * /

              int set_bit_no;

        

              int i;

              x = 0;

              y = 0;

        

              xor1 = arr[0];

        

              / * Получить xor всех элементов массива * /

              for (i = 1; i < n; i++)

                  xor1 = xor1 ^ arr[i];

        

              / * XOR предыдущий результат с числами из

              От 1 до n * /

              for (i = 1; i <= n; i++)

                  xor1 = xor1 ^ i;

        

              / * Получить самый правый установленный бит в set_bit_no * /

              set_bit_no = xor1 & ~(xor1 - 1);

        

              / * Теперь разделите элементы на два набора, сравнивая

              крайний правый бит xor1 с битом

              положение в каждом элементе. Кроме того, получите XOR двух

              наборы. Два XOR являются выходными элементами.

              следующие две петли служат цели * /

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

                  if ((arr[i] & set_bit_no) != 0)

        

                      / * arr [i] принадлежит первому набору * /

                      x = x ^ arr[i];

        

                  else

        

                      / * arr [i] принадлежит второму набору * /

                      y = y ^ arr[i];

              }

              for (i = 1; i <= n; i++) {

                  if ((i & set_bit_no) != 0)

        

                      / * я принадлежу к первому набору * /

                      x = x ^ i;

        

                  else

        

                      / * я принадлежу ко второму набору * /

                      y = y ^ i;

              }

        

              / * * x и * y содержат нужные выходные элементы * /

          }

        

          // Драйвер программы

          public static void Main()

          {

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

        

              int n = arr.Length;

              getTwoElements(arr, n);

              Console.Write(" The missing element is "

                            + x + "and the "

                            + "repeating number is "

                            + y);

          }

      }

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

      PHP

      <?php
      // PHP-программа для поиска повторяющихся
      // и недостающие элементы

        

      function getTwoElements(&$arr, $n)

      {

        

          / * Будет содержать xor всех элементов

          и цифры от 1 до n * /

          $xor1;

        

          / * Будет иметь только один установленный бит xor1 * /

          $set_bit_no;

        

          $i;

          $x = 0;

          $y = 0;

        

          $xor1 = $arr[0];

        

          / * Получить xor всех элементов массива * /

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

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

        

          / * XOR предыдущий результат с числами

          от 1 до n * /

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

              $xor1 = $xor1 ^ $i;

        

          / * Получить самый правый установленный бит в set_bit_no * /

          $set_bit_no = $xor1 & ~($xor1 - 1);

        

          / * Теперь разделите элементы на два набора, сравнивая

          крайний правый бит xor1 с битом

          положение в каждом элементе. Кроме того, получите XOR двух

          наборы. Два XOR являются выходными элементами.

          следующие две петли служат цели * /

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

          {

              if (($arr[$i] & $set_bit_no) != 0)

                

                  / * arr [i] принадлежит первому набору * /

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

        

              else

                

                  / * arr [i] принадлежит второму набору * /

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

          }

            

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

          {

              if (($i & $set_bit_no) != 0)

                

                  / * я принадлежу к первому набору * /

                  $x = $x ^ $i;

        

              else

                

                  / * я принадлежу ко второму набору * /

                  $y = $y ^ $i;

          }

        

          / * * x и * y содержат нужные выходные элементы * /

          echo("The missing element is " . $x

               " and the repeating number is " . $y);

      }

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

      $arr = array( 1, 3, 4, 5, 1, 6, 2 );

      $n = sizeof($arr);

      getTwoElements($arr, $n);

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

      Выход:

      The missing element is 7 and the repeating number is 5
      

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

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

    6. Метод 6 (использовать карту)

      Подходить:
      Этот метод включает в себя создание Hashtable с помощью Map. При этом элементы сопоставляются с их естественным индексом. В этом процессе, если элемент отображается дважды, то это повторяющийся элемент. И если сопоставления элемента там нет, то это недостающий элемент.

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

      // Java-программа для поиска
      // повторяющиеся и отсутствующие элементы
      // используя Карты

        

      import java.util.*;

        

      public class Test1 {

        

          public static void main(String[] args)

          {

        

              int[] arr = { 4, 3, 6, 2, 1, 1 };

        

              Map<Integer, Boolean> numberMap

                  = new HashMap<>();

        

              int max = arr.length;

        

              for (Integer i : arr) {

        

                  if (numberMap.get(i) == null) {

                      numberMap.put(i, true);

                  }

                  else {

                      System.out.println("Repeating = " + i);

                  }

              }

              for (int i = 1; i <= max; i++) {

                  if (numberMap.get(i) == null) {

                      System.out.println("Missing = " + i);

                  }

              }

          }

      }

      Выход:

      Repeating = 1
      Missing = 5
      
    7. Метод 7 (Составьте два уравнения, используя сумму и сумму квадратов)

      Подходить:

      1. Пусть x будет отсутствующим и y будет повторяющимся элементом.
      2. Пусть N — размер массива.
      3. Получить сумму всех чисел по формуле S = N (N + 1) / 2
      4. Получить произведение всех чисел, используя формулу Sum_Sq = N (N + 1) (2N + 1) / 6
      5. Итерация по циклу от i = 1… .N
      6. S — = A [i]
      7. Sum_Sq — = (A [i] * A [i])
      8. Это даст два уравнения
      9. xy = S — (1)
        x ^ 2 — y ^ 2 = Sum_sq
        x + y = (Sum_sq / S) — (2)

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

      #include <bits/stdc++.h> 

        

      using namespace std;

        

      vector<int>repeatedNumber(const vector<int> &A) {

          long long int len = A.size();

          long long int Sum_N = (len * (len+1) ) /2, Sum_NSq = (len * (len +1) *(2*len +1) )/6;

          long long int missingNumber=0, repeating=0;

            

          for(int i=0;i<A.size(); i++){

             Sum_N -= (long long int)A[i];

             Sum_NSq -= (long long int)A[i]*(long long int)A[i];

          }

            

          missingNumber = (Sum_N + Sum_NSq/Sum_N)/2;

          repeating= missingNumber - Sum_N;

          vector <int> ans;

          ans.push_back(repeating);

          ans.push_back(missingNumber);

          return ans;

            
      }

        

        

      int main(void){

              std::vector<int> v = {4, 3, 6, 2, 1, 6,7};

          vector<int> res = repeatedNumber(v);

          for(int x: res){

              cout<< x<<"  ";

          }

          cout<<endl;

      }

    8. Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

      Найти повторяющееся и пропавшее | Добавлено 3 новых метода

      0.00 (0%) 0 votes