Nombre de sous-tableaux de taille K qui est une permutation de nombres de 1 à K

Étant donné un tableau arr d’entiers distincts, la tâche consiste à trouver le nombre de sous-tableaux de taille je ayant tous les éléments de 1 à moien d’autres termes, le sous-tableau est toute permutation d’éléments de 1 à moiavec 1 < = je <= N.

Exemples:

Saisir: arr[] = {2, 3, 1, 5, 4}
Production: 3
Explication:
nous avons {1}, {2, 3, 1} et {2, 3, 1, 5, 4} sous-tableau pour i=1, i=3, i=5 respectivement.
La permutation de la taille 4 et de la taille 2 ne peut pas être effectuée car 5 et 3 gênent respectivement.

Saisir: arr[] = {1, 3, 5, 4, 2}
Production: 2
Explication:
nous avons les sous-tableaux {1} et {1, 3, 5, 4, 2} pour i=1 et i=5 respectivement.

UN Approche naïve est de partir de chaque index et d’essayer de trouver le sous-tableau de chaque taille (i) et de vérifier si tous les éléments de 1 à i sont présents.
Complexité temporelle : O(N2)

Un Approche efficace peut être donné en vérifiant s’il est possible de créer un sous-tableau de taille je pour chaque valeur de i de 1 à N.
Comme nous le savons, chaque sous-tableau de taille K doit être une permutation de tous les éléments de 1 à Ksachant qu’on peut regarder l’index des nombres de 1 à N dans l’ordre et calculer l’indice des valeurs minimales et maximales à chaque étape.

  • Si maximum_ind – minimum_ind + 1 = Kalors on a une permutation de taille K, sinon non.
  • Mettez à jour la valeur de minimum_ind et maximum_ind à chaque étape.

Complexité temporelle : Sur)
Illustration:

Étant donné Arr = {2, 3, 1, 5, 4}commençons par min_ind = INF et max_ind = -1

  1. l’indice de 1 est 2, donc min_ind = min(min_ind, 2) = 2 et max_ind = max(max_ind, 2) = 2,
    2-2+1 = 1 donc on a une permutation de taille 1
  2. l’indice de 2 est 0, donc min_ind = min(min_ind, 0) = 0 et max_ind = max(max_ind, 0) = 2,
    2-0+1 = 3 donc on n’a pas de permutation de taille 2
  3. l’indice de 3 est 1, donc min_ind = min(min_ind, 1) = 0 et max_ind = max(max_ind, 1) = 2,
    2-0+1 = 3 donc on a une permutation de taille 3
  4. l’indice de 4 est 4, donc min_ind = min(min_ind, 4) = 0 et max_ind = max(max_ind, 4) = 4,
    4-0+1 = 5 donc on n’a pas de permutation de taille 4
  5. l’indice de 5 est 3, donc min_ind = min(min_ind, 3) = 0 et max_ind = max(max_ind, 4) = 4,
    4-0+1 = 5 donc on a une permutation de taille 5

Donc la réponse est 3

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

C++

#include <iostream>

#include <unordered_map>

#include <vector>

using namespace std;

int find_permutations(vector<int>& arr)

{

    int cnt = 0;

    int max_ind = -1, min_ind = 10000000;

    int n = arr.size();

    unordered_map<int, int> index_of;

    

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

        index_of[arr[i]] = i + 1;

    }

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

        

        

        

        max_ind = max(max_ind, index_of[i]);

        min_ind = min(min_ind, index_of[i]);

        if (max_ind - min_ind + 1 == i)

            cnt++;

    }

    return cnt;

}

int main()

{

    vector<int> nums;

    nums.push_back(2);

    nums.push_back(3);

    nums.push_back(1);

    nums.push_back(5);

    nums.push_back(4);

    cout << find_permutations(nums);

    return 0;

}

Java

import java.util.*;

class GFG{

    

public static int find_permutations(

    Vector<Integer> arr)

{

    int cnt = 0;

    int max_ind = -1, min_ind = 10000000;

    int n = arr.size();

    

    HashMap<Integer,

            Integer> index_of = new HashMap<>();

            

    

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

    {

        index_of.put(arr.get(i), i + 1);

    }

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

    {

        

        

        

        

        max_ind = Math.max(max_ind, index_of.get(i));

        min_ind = Math.min(min_ind, index_of.get(i));

        

        if (max_ind - min_ind + 1 == i)

            cnt++;

    }

    return cnt;

}

public static void main(String[] args)

{

    Vector<Integer> nums = new Vector<Integer>();

    nums.add(2);

    nums.add(3);

    nums.add(1);

    nums.add(5);

    nums.add(4);

    

    System.out.print(find_permutations(nums));

}

}

Python3

def find_permutations(arr):

    

    cnt = 0

    max_ind = -1

    min_ind = 10000000;

    

    n = len(arr)

    index_of = {}

    

    for i in range(n):

        index_of[arr[i]] = i + 1

    for i in range(1, n + 1):

        

        

        

        max_ind = max(max_ind, index_of[i])

        min_ind = min(min_ind, index_of[i])

        

        if (max_ind - min_ind + 1 == i):

            cnt += 1

            

    return cnt

if __name__ == "__main__":

    nums = []

    nums.append(2)

    nums.append(3)

    nums.append(1)

    nums.append(5)

    nums.append(4)

    print(find_permutations(nums))

C#

using System;

using System.Collections;

using System.Collections.Generic;

class GFG{

    

static int find_permutations(ArrayList arr)

{

    int cnt = 0;

    int max_ind = -1, min_ind = 10000000;

    int n = arr.Count;

    

    Dictionary<int,

               int> index_of = new Dictionary<int,

                                              int>();

            

    

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

    {

        Indice de[(int)arr[i]]= je + 1 ;

    }

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

    {

        

        

        

        

        max_ind = Math.Max(max_ind, index_of[i]);

        min_ind = Math.Min(min_ind, index_of[i]);

        

        if (max_ind - min_ind + 1 == i)

            cnt++;

    }

    return cnt;

}

public static void Main(string[] args)

{

    ArrayList nums = new ArrayList();

    nums.Add(2);

    nums.Add(3);

    nums.Add(1);

    nums.Add(5);

    nums.Add(4);

    Console.Write(find_permutations(nums));

}

}

Javascript

<script>

function find_permutations(arr)

{

    var cnt = 0;

    var max_ind = -1, min_ind = 10000000;

    var n = arr.length;

    var index_of = new Map();

  

    

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

        index_of.set(arr[i], i + 1);

    }

  

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

  

        

        

        

        max_ind = Math.max(max_ind, index_of.get(i));

        min_ind = Math.min(min_ind, index_of.get(i));

        if (max_ind - min_ind + 1 == i)

            cnt++;

    }

  

    return cnt;

}

 

var nums = [];

nums.push(2);

nums.push(3);

nums.push(1);

nums.push(5);

nums.push(4);

document.write(find_permutations(nums));

</script>

Laisser un commentaire

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

Aller en haut