Рубрики

Найти дубликаты за O (n) времени и O (1) лишних пробелов | Комплект 1

Дан массив из n элементов, который содержит элементы от 0 до n-1, причем любое из этих чисел появляется любое количество раз. Найти эти повторяющиеся числа в O (n) и использовать только постоянное пространство памяти.

Например, пусть n будет 7, а массив {1, 2, 3, 1, 3, 6, 6}, ответ должен быть 1, 3 и 6.

Эта проблема является расширенной версией следующей проблемы.

Найти два повторяющихся элемента в данном массиве

Способ 1 и способ 2 вышеуказанной ссылки не применимы, так как в вопросе говорится о O (n) сложности времени и O (1) постоянном пространстве. Кроме того, способ 3 и способ 4 не могут быть применены здесь, потому что в этой задаче может быть более 2 повторяющихся элементов. Метод 5 может быть расширен, чтобы работать для этой проблемы. Ниже приведено решение, аналогичное методу 5.

Алгоритм:

traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

Реализация:

C ++

// код C ++ для поиска
// дублирует за O (n) время
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати дубликатов

void printRepeating(int arr[], int size)

{

int i;

cout << "The repeating elements are:" << endl;

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

{

    if (arr[abs(arr[i])] >= 0)

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

    else

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

}
}

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

int main()

{

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

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

    printRepeating(arr, arr_size);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// код C для поиска
// дублирует за O (n) время
#include <stdio.h>
#include <stdlib.h>

  
// Функция для печати дубликатов

void printRepeating(int arr[], int size)

{

  int i;

  printf("The repeating elements are: \n");

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

  {

    if (arr[abs(arr[i])] >= 0)

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

    else

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

  }

}

  

int main()

{

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

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

  printRepeating(arr, arr_size);

  getchar();

  return 0;

}

Джава

// Java-код для поиска
// дублирует за O (n) время

  

class FindDuplicate

{

 // Функция для печати дубликатов

    void printRepeating(int arr[], int size)

    {

        int i;  

        System.out.println("The repeating elements are : ");

     

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

        {

            if (arr[ Math.abs(arr[i])] >= 0)

                arr[ Math.abs(arr[i])] = -arr[ Math.abs(arr[i])];

            else

                System.out.print(Math.abs(arr[i]) + " ");

        }         

    

  

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

    public static void main(String[] args) 

    {

        FindDuplicate duplicate = new FindDuplicate();

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

        int arr_size = arr.length;

  

        duplicate.printRepeating(arr, arr_size);

    }

}

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

python3

# Python3 код для поиска
# дубликатов за O (n) время

  
# Функция для печати дубликатов

def printRepeating(arr, size):

      

    print("The repeating elements are: ")

      

    for i in range(0, size):

          

        if arr[abs(arr[i])] >= 0:

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

        else:

            print (abs(arr[i]), end = " ")

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

arr = [1, 2, 3, 1, 3, 6, 6]

arr_size = len(arr)

  
printRepeating(arr, arr_size)

  
# Этот код предоставлен Shreyanshi Arun.

C #

// код C # для поиска
// дублирует за O (n) время

using System;

  

class GFG

{

    static void printRepeating(int []arr,

                            int size)

    {

        int i; 

          

        Console.Write("The repeating"

                       " elements are : ");

      

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

        {

            if (arr[ Math.Abs(arr[i])] >= 0)

                arr[ Math.Abs(arr[i])] =

                    -arr[ Math.Abs(arr[i])];

            else

                Console.Write(Math.Abs(arr[i]) + " ");

        }         

    

  

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

    public static void Main() 

    {

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

        int arr_size = arr.Length;

  

        printRepeating(arr, arr_size);

    }

}

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

PHP

<?php
// PHP-программа для поиска дубликатов в O (n)
// время и O (1) дополнительное пространство | Комплект 1

  

function printRepeating($arr, $size)

{

  

    echo "The repeating elements are: \n";

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

    {

        if ($arr[abs($arr[$i])] >= 0)

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

        else

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

    }

}

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

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

$arr_size = count($arr);

printRepeating($arr, $arr_size);

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

Выход:

The repeating elements are:
1  3  6

Примечание. Приведенная выше программа не обрабатывает регистр 0 (если в массиве присутствует 0). Программа может быть легко изменена, чтобы справиться с этим также. Это не обрабатывается, чтобы сохранить код простым.

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

Существует проблема в вышеупомянутом подходе. Он печатает повторный номер более одного раза. Например: {1, 6, 3, 1, 3, 6, 6} он выдаст вывод в виде: 1 3 6 6. В нижеприведенном наборе обсуждается другой подход, который печатает повторяющиеся элементы только один раз.

Дублирует массив в O (n) и использует O (1) лишний пробел | Set-2

Другой код O (n) & O (1):

C ++

// код C ++ для поиска
// дублирует за O (n) время
#include <bits/stdc++.h>

using namespace std;

  

int main()

{

      

    int numRay[] = {0, 4, 3, 2, 7, 8, 2, 3, 1};

    int arr_size = sizeof(numRay) / 

                   sizeof(numRay[0]); 

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

    {

        numRay[numRay[i] % 10] = numRay[numRay[i] % 10] + 10;

    }

    cout << "The repeating elements are : " << endl;

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

    {

        if (numRay[i] > 19) 

        {

            cout << i << " " << endl;

        }

    }

    return 0;

}

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

Джава

class Leet442 {

  

    public static void main(String args[]) {

        int numRay[] = {0, 4, 3, 2, 7, 8, 2, 3, 1};

  

        for (int i = 0; i < numRay.length; i++) {

            numRay[numRay[i] % 10] = numRay[numRay[i] % 10] + 10;

        }

        System.out.println("The repeating elements are : ");

        for (int i = 0; i < numRay.length; i++) {

            if (numRay[i] > 19) {

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

            }

        }

    }

}

python3

# Python3 код для поиска дубликатов за O (n) время

numRay = [0, 4, 3, 2, 7, 8, 2, 3, 1];

arr_size = len(numRay); 

for i in range(arr_size):

  

    numRay[numRay[i] % 10] = numRay[numRay[i] % 10] + 10;

  

print("The repeating elements are : ");

for i in range(arr_size):

    if (numRay[i] > 19): 

        print(i, " ");

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

C #

using System;

      

class GFG

{

    public static void Main(String []args)

    {

        int []numRay1 = {0, 4, 3, 2, 7, 8, 2, 3, 1};

  

        for(int i = 0; i < numRay1.Length; i++)

            numRay1[numRay1[i] % 10] = numRay1[numRay1[i] % 10] + 10;

  

        Console.WriteLine("The repeating elements are : "); 

  

        for(int i = 0; i < numRay1.Length; i++)

            if(numRay1[i] > 19)

                Console.WriteLine(i + " ");                                         

    

}

  
// Этот код предоставлен Rajput-Ji

Выход:

The repeating elements are : 
2 
3

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

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

Найти дубликаты за O (n) времени и O (1) лишних пробелов | Комплект 1

0.00 (0%) 0 votes