Nombre minimum de suppressions pour faire une séquence triée

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Soit un tableau de n entiers. La tâche consiste à supprimer ou supprimer le nombre minimum d’éléments du tableau de sorte que lorsque les éléments restants sont placés dans le même ordre de séquence pour former un séquence triée croissante.
Exemples :

Input : {5, 6, 1, 7, 4}
Output : 2
Removing 1 and 4
leaves the remaining sequence order as
5 6 7 which is a sorted sequence.

Input : {30, 40, 2, 5, 1, 7, 45, 50, 8}
Output : 4

UN solutions simples est de supprimer toutes les sous-séquences un par un et vérifiez si l’ensemble d’éléments restant est dans l’ordre trié ou non. La complexité temporelle de cette solution est exponentielle.
Un approche efficace utilise le concept de trouver la longueur de la plus longue sous-suite croissante d’une séquence donnée.
Algorithme:

-->arr be the given array.
-->n number of elements in arr.
-->len be the length of longest
   increasing subsequence in arr.
-->// minimum number of deletions
   min = n - len

C++

#include <bits/stdc++.h>

using namespace std;

   

   

int lis( int arr[], int n )

{

    int result = 0;

    int lis[n];

    

    

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

        lis[i] = 1;

    

       

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

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

            if ( arr[i] > arr[j] &&

                 lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

    

    

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

        if (result < lis[i])

            result = lis[i];

    return result;

}

int minimumNumberOfDeletions(int arr[],

                             int n)

{

    

    

    int len = lis(arr, n);

    

    

    

    return (n - len);

}

int main()

{

    int arr[] = {30, 40, 2, 5, 1,

                   7, 45, 50, 8};

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

    cout << "Minimum number of deletions = "

         << minimumNumberOfDeletions(arr, n);

    return 0;

}

Java

class GFG

{

    

    

    

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

    {

        int result = 0;

        int[] lis = new int[n];

    

        

        

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

            lis[i] = 1;

    

        

           

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

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

                if ( arr[i] > arr[j] &&

                    lis[i] < lis[j] + 1)

                    lis[i] = lis[j] + 1;

    

        

        

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

            if (result < lis[i])

                result = lis[i];

    

        return result;

    }

    

    

    

    static int minimumNumberOfDeletions(int arr[],

                                        int n)

    {

        

        

        int len = lis(arr, n);

    

        

        

        

        return (n - len);

    }

    

    public static void main (String[] args)

    {

        int arr[] = {30, 40, 2, 5, 1,

                       7, 45, 50, 8};

        int n = arr.length;

        System.out.println("Minimum number of" +

                               " deletions = " +

              minimumNumberOfDeletions(arr, n));

    }

}

Python3

def lis(arr, n):

    result = 0

    lis = [0 for i in range(n)]

    

    

    for i in range(n):

        lis[i] = 1

    

    

    for i in range(1, n):

        for j in range(i):

            if ( arr[i] > arr[j] and

                lis[i] < lis[j] + 1):

                lis[i] = lis[j] + 1

    

    

    for i in range(n):

        if (result < lis[i]):

            result = lis[i]

    return result

def minimumNumberOfDeletions(arr, n):

    

    

    len = lis(arr, n)

    

    

    

    return (n - len)

arr = [30, 40, 2, 5, 1,

          7, 45, 50, 8]

n = len(arr)

print("Minimum number of deletions = ",

      minimumNumberOfDeletions(arr, n))

        

C#

using System;

class GfG

{

    

    

    

    

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

    {

        int result = 0;

        int[] lis = new int[n];

    

        

        

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

            lis[i] = 1;

    

        

        

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

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

                if ( arr[i] > arr[j] &&

                     lis[i] < lis[j] + 1)

                  lis[i] = lis[j] + 1;

    

        

        

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

            if (result < lis[i])

                result = lis[i];

    

        return result;

    }

    

    

    

    static int minimumNumberOfDeletions(

                        int []arr, int n)

    {

        

        

        

        int len = lis(arr, n);

    

        

        

        

        return (n - len);

    }

    

    public static void Main (String[] args)

    {

        int []arr = {30, 40, 2, 5, 1,

                       7, 45, 50, 8};

        int n = arr.Length;

        Console.Write("Minimum number of" +

                          " deletions = " +

         minimumNumberOfDeletions(arr, n));

    }

}

PHP

<?php

   

   

function lis( $arr, $n )

{

    $result = 0;

    $lis[$n] = 0 ;

    

       

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

        $lis[$i] = 1 ;

    

       

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

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

            if ( $arr[$i] > $arr[$j] &&

                $lis[$i] < $lis[$j] + 1)

                $lis[$i] = $lis[$j] + 1 ;

    

    

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

        if ($result < $lis[$i])

            $result = $lis[$i];

    return $result;

}

function minimumNumberOfDeletions($arr, $n)

{

    

    

    $len = lis($arr, $n);

    

    

    

    return ($n - $len);

}

$arr = array(30, 40, 2, 5, 1,

               7, 45, 50, 8);

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

echo "Minimum number of deletions = " ,

    minimumNumberOfDeletions($arr, $n);

?>

Javascript

<script>

function lis(arr,n)

{

    let result = 0;

    let lis= new Array(n);

    

    

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

        lis[i] = 1;

    

    

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

        for (let j = 0; j < i; j++ )

            if ( arr[i] > arr[j] &&

                lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

    

    

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

        if (result < lis[i])

            result = lis[i];

    return result;

}

function minimumNumberOfDeletions(arr,n)

{

    

    

    let len = lis(arr,n);

    

    

    

    return (n - len);

}

    let arr = [30, 40, 2, 5, 1,7, 45, 50, 8];

    let n = arr.length;

    document.write("Minimum number of deletions = "

    + minimumNumberOfDeletions(arr,n));

</script>

Production :

Minimum number of deletions = 4 

Complexité temporelle : Sur2)
La complexité temporelle peut être réduite à O(nlogn) en trouvant le Taille de sous-séquence croissante la plus longue (N Log N)
Cet article est contribué par Ayush Jauhari. Si vous aimez GeeksforGeeks et que vous souhaitez contribuer, vous pouvez également écrire un article en utilisant écrire.geeksforgeeks.org ou envoyez votre article à contribute@geeksforgeeks.org. Voyez votre article apparaître sur la page principale de GeeksforGeeks et aidez les autres Geeks.
Veuillez écrire des commentaires si vous trouvez quelque chose d'incorrect ou si vous souhaitez partager plus d'informations sur le sujet abordé ci-dessus.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *