Dans cet article, nous allons explorer comment décaler toutes les valeurs non nulles d'un tableau vers la droite tout en conservant leur ordre relatif. Ce problème est une question d'entretien courante qui teste votre compréhension de la manipulation des tableaux et de l'optimisation des algorithmes. Plongeons dans la solution utilisant Java.
Si vous n'êtes pas familier avec les concepts de base des tableaux, je vous recommande de consulter Comprendre les bases des tableaux en Java : un guide simple pour vous mettre à jour !
Étant donné un tableau d'entiers, nous souhaitons décaler toutes les valeurs non nulles vers la droite tout en préservant leur ordre. Les valeurs zéro doivent être déplacées vers la gauche.
Exemple :
Input: [1, 2, 0, 3, 0, 0, 4, 0, 2, 9] Output: [0, 0, 0, 0, 1, 2, 3, 4, 2, 9]
Nous utiliserons une approche de suivi d'index pour résoudre ce problème. Le but est de parcourir le tableau de droite à gauche et de déplacer les éléments non nuls vers leurs positions correctes.
Cette approche a une complexité temporelle de O(n) et une complexité spatiale de O(1), ce qui la rend à la fois efficace et peu encombrante.
package arrays; // Time Complexity - O(n) // Space Complexity - O(1) public class ShiftNonZeroValuesToRight { private void shiftValues(int[] inputArray) { /* Variable to keep track of index position to be filled with Non-Zero Value */ int pointer = inputArray.length - 1; // If value is Non-Zero then place it at the pointer index for (int i = pointer; i >= 0; i--) { /* If there is a non-zero already at correct position, just decrement position */ if (inputArray[i] != 0) { if (i != pointer) { inputArray[pointer] = inputArray[i]; inputArray[i] = 0; } pointer--; } } // Printing result using for-each loop for (int i : inputArray) { System.out.print(i); } System.out.println(); } public static void main(String[] args) { // Test-Case-1 : Ending with a Non-Zero int input1[] = { 1, 2, 0, 3, 0, 0, 4, 0, 2, 9 }; // Test-Case-2 : Ending with Zero int input2[] = { 8, 5, 1, 0, 0, 5, 0 }; // Test-Case-3 : All Zeros int input3[] = { 0, 0, 0, 0 }; // Test-Case-4 : All Non-Zeros int input4[] = { 1, 2, 3, 4 }; // Test-Case-5 : Empty Array int input5[] = {}; // Test-Case-6 : Empty Array int input6[] = new int[5]; // Test-Case-7 : Uninitialized Array int input7[]; ShiftNonZeroValuesToRight classObject = new ShiftNonZeroValuesToRight(); classObject.shiftValues(input1); // Result : 0000123429 classObject.shiftValues(input2); // Result : 0008515 classObject.shiftValues(input3); // Result : 0000 classObject.shiftValues(input4); // Result : 1234 classObject.shiftValues(input5); // Result : classObject.shiftValues(input6); // Result : 00000 classObject.shiftValues(input7); // Result : Compilation Error - Array may not have been initialized } }
Tableaux vides : Le programme gère les tableaux vides sans lever d'exception.
Tableaux non initialisés : Décommenter le scénario de test pour les tableaux non initialisés entraînera une erreur de compilation, démontrant l'importance de l'initialisation du tableau.
Ce programme fournit un moyen efficace de décaler des valeurs non nulles vers la droite dans un tableau. C'est un excellent exemple de la façon dont une gestion minutieuse des pointeurs peut conduire à des solutions optimales en termes de complexité temporelle et spatiale.
Pour une autre question d'entretien courante sur les tableaux, consultez mon article précédent sur le déplacement des valeurs non nulles vers la gauche : un problème d'entretien de tableau courant-1
Si vous avez des questions ou des suggestions, n'hésitez pas à laisser un commentaire ci-dessous. Bon codage !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!