![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant.png)
Étant donné deux tableaux non croissants UNE[] et B[] de taille N, la tâche consiste à trouver la distance maximale entre je et j tel que je j et UNE[i] B[j].
Exemples:
Saisir: UNE[] = {2, 2, 2}, B[] = {10, 10, 1}
Sortir: 1
Explication:
Les paires valides satisfaisant les conditions sont (0, 0), (0, 1) et (1, 1).
Par conséquent, la distance maximale est de 1 entre les indices 0 de A[] et 1 de B[].
Saisir: UNE[] = {55, 30, 5, 4, 2}, B[] = {100, 20, 10, 10, 5}
Sortir: 2
Explication:
Les paires valides satisfaisant les conditions sont (0, 0), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4) et (4, 4).
Par conséquent, la distance maximale est de 2 entre les indices 2 de A[] et 4 de B[].
Approche naïve : L’approche la plus simple pour résoudre le problème est de parcourir le tableau A[] et pour chaque élément de A[] parcourir le tableau B[] et trouver la distance maximale entre les points tels que j>=i et B[j] >= Un[i].
Complexité temporelle : O(N2)
Espace auxiliaire : O(1)
Approche efficace : L’approche ci-dessus peut être optimisée davantage en utilisant l’algorithme de recherche binaire. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser une variable, disons ans comme 0 pour stocker la distance maximale entre deux éléments dans deux tableaux non croissants.
- Itérer dans la plage [0, N-1] en utilisant la variable je, et effectuez les étapes suivantes :
- Initialisez deux variables, disons meugler comme je, haut comme N-1.
- Itérer jusqu’à meugler est inférieur ou égal à haute et procédez comme suit:
- Initialiser une variable, disons milieu comme bas+(haut-bas)/2.
- Si UNE[i] est inférieur à égal à B[mid], puis mettre à jour ans à max de ans et mi-je et meugler à milieu+1.
- Sinon, mettez à jour haute à mi-1.
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans comme réponse
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
Table des matières
C++
|
#include en utilisant l’espace de noms std ; int Distancemax(int A[], entier B[], entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } int main() { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; entier N = 3; cout << maxDistance (A, B, N); } |
Java
|
classe publique GFG { static int maxDistance(int A[], entier B[], entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = Math.max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } public static void main(String[] arguments) { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; entier N = 3; System.out.println(maxDistance(A, B, N)); } } |
Python3
|
def maxDistance (A, B, N): ans = 0 pour i dans la plage (N): faible = je élevé = N – 1 tandis que (faible <= élevé): moyen = bas + (haut – bas) // 2 si un[i] <= B[mid]): ans = max(ans, milieu – i) bas = moyen + 1 autre: haut = moyen – 1 retour et if __name__ == ‘__main__’ : A = [ 2, 2, 2 ] B = [ 10, 10, 1 ] N = 3 print(MaxDistance(A, B, N)) |
C#
|
en utilisant le système ; en utilisant System.Collections.Generic ; classe publique GFG{ static int maxDistance(int[] A, int[] B, entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = Math.Max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } public statique vide Main() { entier[] A = { 2, 2, 2 } ; entier[] B = { 10, 10, 1 } ; entier N = 3; Console.Write(maxDistance(A, B, N)); } } |
Javascript
Complexité temporelle : O(N×log(N))
Espace auxiliaire : O(1)
Approche efficace : L’approche ci-dessus peut être optimisée davantage en utilisant la technique à deux pointeurs. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser deux variables, dire, je, et j effectuer un pointeur à deux.
- Itérer jusqu’à je et j sont inférieurs à N et effectuez les étapes suivantes:
- Si UNE[i] est supérieur à B[j], puis incrémenter je par 1, car les tableaux sont triés par ordre non croissant.
- Sinon, mettez à jour ans à max de ans et ji, et incrémenter j par 1.
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans comme réponse.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int Distancemax(int A[], entier B[], entier N) { entier i = 0, j = 0; int ans = 0; tandis que (i < N && j < N) { si un[i] > B[j]) { ++i; } autre { ans = max(ans, j – i); j++; } } retour ans; } int main() { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; int N = taillede(A) / taillede(A[0]); cout << maxDistance (A, B, N); } |
Java
|
importer java.io.*; classe GFG { static int maxDistance(int A[], entier B[], entier N) { entier i = 0, j = 0; int ans = 0; tandis que (i < N && j < N) { si un[i] > B[j]) { ++i; } autre { ans = Math.max(ans, j – i); j++; } } retour ans; } public static void main (String[] arguments) { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; int N = A.longueur; System.out.println(maxDistance(A, B, N)); } } |
Python3
|
def maxDistance (A, B, N): je = 0 j = 0 ans = 0 tandis que (i < N et j < N) : si un[i] >… |
Étant donné deux tableaux non croissants UNE[] et B[] de taille N, la tâche consiste à trouver la distance maximale entre je et j tel que je j et UNE[i] B[j].
Exemples:
Saisir: UNE[] = {2, 2, 2}, B[] = {10, 10, 1}
Sortir: 1
Explication:
Les paires valides satisfaisant les conditions sont (0, 0), (0, 1) et (1, 1).
Par conséquent, la distance maximale est de 1 entre les indices 0 de A[] et 1 de B[].
Saisir: UNE[] = {55, 30, 5, 4, 2}, B[] = {100, 20, 10, 10, 5}
Sortir: 2
Explication:
Les paires valides satisfaisant les conditions sont (0, 0), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4) et (4, 4).
Par conséquent, la distance maximale est de 2 entre les indices 2 de A[] et 4 de B[].
Approche naïve : L’approche la plus simple pour résoudre le problème est de parcourir le tableau A[] et pour chaque élément de A[] parcourir le tableau B[] et trouver la distance maximale entre les points tels que j>=i et B[j] >= Un[i].
Complexité temporelle : O(N2)
Espace auxiliaire : O(1)
Approche efficace : L’approche ci-dessus peut être optimisée davantage en utilisant l’algorithme de recherche binaire. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser une variable, disons ans comme 0 pour stocker la distance maximale entre deux éléments dans deux tableaux non croissants.
- Itérer dans la plage [0, N-1] en utilisant la variable je, et effectuez les étapes suivantes :
- Initialisez deux variables, disons meugler comme je, haut comme N-1.
- Itérer jusqu’à meugler est inférieur ou égal à haute et procédez comme suit:
- Initialiser une variable, disons milieu comme bas+(haut-bas)/2.
- Si UNE[i] est inférieur à égal à B[mid], puis mettre à jour ans à max de ans et mi-je et meugler à milieu+1.
- Sinon, mettez à jour haute à mi-1.
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans comme réponse
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int Distancemax(int A[], entier B[], entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } int main() { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; entier N = 3; cout << maxDistance (A, B, N); } |
Java
|
classe publique GFG { static int maxDistance(int A[], entier B[], entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = Math.max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } public static void main(String[] arguments) { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; entier N = 3; System.out.println(maxDistance(A, B, N)); } } |
Python3
|
def maxDistance (A, B, N): ans = 0 pour i dans la plage (N): faible = je élevé = N – 1 tandis que (faible <= élevé): moyen = bas + (haut – bas) // 2 si un[i] <= B[mid]): ans = max(ans, milieu – i) bas = moyen + 1 autre: haut = moyen – 1 retour et if __name__ == ‘__main__’ : A = [ 2, 2, 2 ] B = [ 10, 10, 1 ] N = 3 print(MaxDistance(A, B, N)) |
C#
|
en utilisant le système ; en utilisant System.Collections.Generic ; classe publique GFG{ static int maxDistance(int[] A, int[] B, entier N) { int ans = 0; pour (int i = 0; i < N; i++) { int bas = i, haut = N – 1 ; tandis que (faible <= élevé) { int moyen = bas + (haut – bas) / 2 ; si un[i] <= B[mid]) { ans = Math.Max(ans, milieu – i); faible = moyen + 1 ; } autre { élevé = moyen – 1 ; } } } retour ans; } public statique vide Main() { entier[] A = { 2, 2, 2 } ; entier[] B = { 10, 10, 1 } ; entier N = 3; Console.Write(maxDistance(A, B, N)); } } |
Javascript
Complexité temporelle : O(N×log(N))
Espace auxiliaire : O(1)
Approche efficace : L’approche ci-dessus peut être optimisée davantage en utilisant la technique à deux pointeurs. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser deux variables, dire, je, et j effectuer un pointeur à deux.
- Itérer jusqu’à je et j sont inférieurs à N et effectuez les étapes suivantes:
- Si UNE[i] est supérieur à B[j], puis incrémenter je par 1, car les tableaux sont triés par ordre non croissant.
- Sinon, mettez à jour ans à max de ans et ji, et incrémenter j par 1.
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans comme réponse.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int Distancemax(int A[], entier B[], entier N) { entier i = 0, j = 0; int ans = 0; tandis que (i < N && j < N) { si un[i] > B[j]) { ++i; } autre { ans = max(ans, j – i); j++; } } retour ans; } int main() { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; int N = taillede(A) / taillede(A[0]); cout << maxDistance (A, B, N); } |
Java
|
importer java.io.*; classe GFG { static int maxDistance(int A[], entier B[], entier N) { entier i = 0, j = 0; int ans = 0; tandis que (i < N && j < N) { si un[i] > B[j]) { ++i; } autre { ans = Math.max(ans, j – i); j++; } } retour ans; } public static void main (String[] arguments) { int A[] = { 2, 2, 2 } ; int B[] = { 10, 10, 1 } ; int N = A.longueur; System.out.println(maxDistance(A, B, N)); } } |
Python3
|
def maxDistance (A, B, N): je = 0 j = 0 ans = 0 tandis que (i < N et j < N) : si un[i] >… |
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
