Sous-tableau avec différence entre élément maximum et minimum supérieur ou égal à sa longueur

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

Étant donné un tableau arr[], la tâche consiste à trouver un sous-tableau dont la différence entre l’élément maximum et l’élément minimum est supérieure ou égale à la longueur du sous-tableau. Si aucun sous-tableau de ce type n’existe, imprimez -1.
Exemples:

Saisir: arr[] = {3, 7, 5, 1}
Production: 3 7
|3 – 7| > longueur({3, 7}) soit 4 ≥ 2
Saisir: arr[] = {1, 2, 3, 4, 5}
Production: -1
Il n’existe aucun sous-réseau répondant aux critères.

Approche naïve : Trouvez tous les sous-tableaux possibles avec au moins deux éléments, puis vérifiez chacun des sous-tableaux qui satisfont à la condition donnée, c’est-à-dire max (sous-tableau) – min (sous-tableau) ≥ len (sous-tableau)
Approche efficace : Trouvez les sous-tableaux de longueur 2 où la différence absolue entre les deux seuls éléments est supérieure ou égale à 2. Cela couvrira presque tous les cas car il n’y a que trois cas où il n’y a pas de tel sous-tableau :

  1. Lorsque la longueur du tableau est 0.
  2. Lorsque tous les éléments du tableau sont égaux.
  3. Lorsque tous les deux éléments consécutifs du tableau ont une différence absolue de 0 ou 1.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

void findSubArr(int arr[], int n)

{

    

    for (int i = 0; i < n - 1; i++) {

        

        

        if (abs(arr[i] - arr[i + 1]) >= 2) {

            cout << arr[i] << " " << arr[i + 1];

            return;

        }

    }

    

    cout << -1;

}

int main()

{

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

    int n = sizeof(arr) / sizeof(int);

    findSubArr(arr, n);

    return 0;

}

Java

class GFG

{

    

    

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

    {

    

        

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

        {

    

            

            

            if (Math.abs(arr[i] - arr[i + 1]) >= 2)

            {

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

                return;

            }

        }

    

        

        System.out.print(-1);

    }

    

    

    public static void main (String[] args)

    {

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

        int n = arr.length;

    

        findSubArr(arr, n);

    }

}

Python3

def findSubArr(arr, n) :

    

    for i in range(n - 1) :

        

        

        if (abs(arr[i] - arr[i + 1]) >= 2) :

            print(arr[i] ,arr[i + 1],fin="");

            return;

    

    print(-1);

if __name__ == "__main__" :

    arr = [ 1, 2, 4, 6, 7 ];

    n = len(arr);

    findSubArr(arr, n);

C#

using System;

class GFG

{

    

    

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

    {

    

        

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

        {

    

            

            

            if (Math.Abs(arr[i] - arr[i + 1]) >= 2)

            {

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

                return;

            }

        }

    

        

        Console.Write(-1);

    }

    

    

    public static void Main()

    {

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

        int n = arr.Length;

    

        findSubArr(arr, n);

    }

}

Javascript

<script>

function findSubArr(arr, n) {

    

    for (let i = 0; i < n - 1; i++) {

        

        

        if (Math.abs(arr[i] - arr[i + 1]) >= 2) {

            document.write(arr[i] + " " + arr[i + 1]);

            return;

        }

    }

    

    document.write(-1);

}

let arr = [1, 2, 4, 6, 7];

let n = arr.length

findSubArr(arr, n);

</script>

Complexité temporelle : SUR)

Laisser un commentaire

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