Traversée de tableaux dans DSA à l'aide de JavaScript : des bases aux techniques avancées

La traversée de tableaux est un concept fondamental des structures de données et des algorithmes (DSA) que tout développeur doit maîtriser. Dans ce guide complet, nous explorerons diverses techniques de parcours de tableaux en JavaScript, en commençant par des approches de base et en progressant vers des méthodes plus avancées. Nous couvrirons 20 exemples, allant du niveau facile au niveau avancé, et inclurons des questions de style LeetCode pour renforcer votre apprentissage.

Table des matières

1. Introduction à la traversée de tableaux
2. Traversée de base du tableau
   • Exemple 1 : Utiliser une boucle for
   • Exemple 2 : Utiliser une boucle while
   • Exemple 3 : Utiliser une boucle do-while
   • Exemple 4 : Traversée inversée
3. Méthodes de tableau JavaScript modernes
   • Exemple 5 : méthode forEach
   • Exemple 6 : méthode map
   • Exemple 7 : méthode de filtrage
   • Exemple 8 : méthode de réduction
4. Techniques de traversée intermédiaire
   • Exemple 9 : Technique à deux points
   • Exemple 10 : Fenêtre coulissante
   • Exemple 11 : L'algorithme de Kadane
   • Exemple 12 : Algorithme du drapeau national néerlandais
5. Techniques de traversée avancées
   • Exemple 13 : Parcours récursif
   • Exemple 14 : Recherche binaire sur un tableau trié
   • Exemple 15 : Fusionner deux tableaux triés
   • Exemple 16 : Algorithme de sélection rapide
6. Traversées spécialisées
   • Exemple 17 : Parcours d'un tableau 2D
   • Exemple 18 : Traversée de matrice en spirale
   • Exemple 19 : Traversée diagonale
   • Exemple 20 : Traversée en zigzag
7. Considérations relatives aux performances
8. Problèmes de pratique LeetCode
9. Conclusion

1. Introduction à la traversée de tableaux

La traversée d'un tableau est le processus consistant à visiter chaque élément d'un tableau pour effectuer une opération. Il s’agit d’une compétence cruciale en programmation, qui constitue la base de nombreux algorithmes et manipulations de données. En JavaScript, les tableaux sont des structures de données polyvalentes qui offrent plusieurs façons de parcourir et de manipuler les données.

2. Traversée de base du tableau

Commençons par les méthodes fondamentales de parcours de tableaux.

Exemple 1 : Utiliser une boucle for

La boucle for classique est l'un des moyens les plus courants de parcourir un tableau.

function sumArray(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

const numbers = [1, 2, 3, 4, 5];
console.log(sumArray(numbers)); // Output: 15

Complexité temporelle : O(n), où n est la longueur du tableau.

Exemple 2 : Utiliser une boucle while

Une boucle while peut également être utilisée pour parcourir un tableau, en particulier lorsque la condition de terminaison est plus complexe.

function findFirstNegative(arr) {
    let i = 0;
    while (i < arr.length && arr[i] >= 0) {
        i++;
    }
    return i < arr.length ? arr[i] : "No negative number found";
}

const numbers = [2, 4, 6, -1, 8, 10];
console.log(findFirstNegative(numbers)); // Output: -1

Complexité temporelle : O(n) dans le pire des cas, mais peut être moindre si un nombre négatif est trouvé tôt.

Exemple 3 : Utiliser une boucle do-while

La boucle do-while est moins courante pour le parcours de tableaux mais peut être utile dans certains scénarios.

function printReverseUntilZero(arr) {
    let i = arr.length - 1;
    do {
        console.log(arr[i]);
        i--;
    } while (i >= 0 && arr[i] !== 0);
}

const numbers = [1, 3, 0, 5, 7];
printReverseUntilZero(numbers); // Output: 7, 5

Complexité temporelle : O(n) dans le pire des cas, mais peut être inférieur si zéro est rencontré tôt.

Exemple 4 : parcours inverse

Le parcours d'un tableau dans l'ordre inverse est une opération courante dans de nombreux algorithmes.

function reverseTraversal(arr) {
    const result = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        result.push(arr[i]);
    }
    return result;
}

const numbers = [1, 2, 3, 4, 5];
console.log(reverseTraversal(numbers)); // Output: [5, 4, 3, 2, 1]

Complexité temporelle : O(n), où n est la longueur du tableau.

3. Méthodes de tableau JavaScript modernes

ES6 et les versions ultérieures de JavaScript ont introduit de puissantes méthodes de tableau qui simplifient le parcours et la manipulation.

Exemple 5 : méthode forEach

La méthode forEach fournit un moyen propre de parcourir les éléments du tableau.

function logEvenNumbers(arr) {
    arr.forEach(num => {
        if (num % 2 === 0) {
            console.log(num);
        }
    });
}

const numbers = [1, 2, 3, 4, 5, 6];
logEvenNumbers(numbers); // Output: 2, 4, 6

Complexité temporelle : O(n), où n est la longueur du tableau.

Exemple 6 : méthode map

La méthode map crée un nouveau tableau avec les résultats de l'appel d'une fonction fournie sur chaque élément.

function doubleNumbers(arr) {
    return arr.map(num => num * 2);
}

const numbers = [1, 2, 3, 4, 5];
console.log(doubleNumbers(numbers)); // Output: [2, 4, 6, 8, 10]

Complexité temporelle : O(n), où n est la longueur du tableau.

Exemple 7 : méthode de filtrage

La méthode filter crée un nouveau tableau avec tous les éléments qui satisfont à une certaine condition.

function filterPrimes(arr) {
    function isPrime(num) {
        if (num <= 1) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    return arr.filter(isPrime);
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(filterPrimes(numbers)); // Output: [2, 3, 5, 7]

Complexité temporelle : O(n * sqrt(m)), où n est la longueur du tableau et m est le plus grand nombre du tableau.

Exemple 8 : méthode de réduction

La méthode de réduction applique une fonction de réduction à chaque élément du tableau, ce qui donne une valeur de sortie unique.

function findMax(arr) {
    return arr.reduce((max, current) => Math.max(max, current), arr[0]);
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMax(numbers)); // Output: 9

Complexité temporelle : O(n), où n est la longueur du tableau.

4. Techniques de traversée intermédiaire

Explorons maintenant quelques techniques intermédiaires pour le parcours de tableaux.

Exemple 9 : Technique à deux pointeurs

La technique à deux pointeurs est souvent utilisée pour résoudre efficacement les problèmes liés aux tableaux.

function isPalindrome(arr) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        if (arr[left] !== arr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

console.log(isPalindrome([1, 2, 3, 2, 1])); // Output: true
console.log(isPalindrome([1, 2, 3, 4, 5])); // Output: false

Time Complexity: O(n/2) which simplifies to O(n), where n is the length of the array.

Example 10: Sliding window

The sliding window technique is useful for solving problems involving subarrays or subsequences.

function maxSubarraySum(arr, k) {
    if (k > arr.length) return null;

    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

const numbers = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSubarraySum(numbers, 4)); // Output: 39

Time Complexity: O(n), where n is the length of the array.

Example 11: Kadane's Algorithm

Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.

function maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

const numbers = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(numbers)); // Output: 6

Time Complexity: O(n), where n is the length of the array.

Example 12: Dutch National Flag Algorithm

This algorithm is used to sort an array containing three distinct elements.

function dutchFlagSort(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }

    return arr;
}

const numbers = [2, 0, 1, 2, 1, 0];
console.log(dutchFlagSort(numbers)); // Output: [0, 0, 1, 1, 2, 2]

Time Complexity: O(n), where n is the length of the array.

5. Advanced Traversal Techniques

Let's explore some more advanced techniques for array traversal.

Example 13: Recursive traversal

Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.

function sumNestedArray(arr) {
    let sum = 0;
    for (let element of arr) {
        if (Array.isArray(element)) {
            sum += sumNestedArray(element);
        } else {
            sum += element;
        }
    }
    return sum;
}

const nestedNumbers = [1, [2, 3], [[4, 5], 6]];
console.log(sumNestedArray(nestedNumbers)); // Output: 21

Time Complexity: O(n), where n is the total number of elements including nested ones.

Example 14: Binary search on sorted array

Binary search is an efficient algorithm for searching a sorted array.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedNumbers, 7)); // Output: 3
console.log(binarySearch(sortedNumbers, 6)); // Output: -1

Time Complexity: O(log n), where n is the length of the array.

Example 15: Merge two sorted arrays

This technique is often used in merge sort and other algorithms.

function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            mergedArray.push(arr1[i]);
            i++;
        } else {
            mergedArray.push(arr2[j]);
            j++;
        }
    }

    while (i < arr1.length) {
        mergedArray.push(arr1[i]);
        i++;
    }

    while (j < arr2.length) {
        mergedArray.push(arr2[j]);
        j++;
    }

    return mergedArray;
}

const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity: O(n + m), where n and m are the lengths of the input arrays.

Example 16: Quick Select Algorithm

Quick Select is used to find the kth smallest element in an unsorted array.

function quickSelect(arr, k) {
    if (k < 1 || k > arr.length) {
        return null;
    }

    function partition(low, high) {
        const pivot = arr[high];
        let i = low - 1;

        for (let j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }

        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }

    function select(low, high, k) {
        const pivotIndex = partition(low, high);

        if (pivotIndex === k - 1) {
            return arr[pivotIndex];
        } else if (pivotIndex > k - 1) {
            return select(low, pivotIndex - 1, k);
        } else {
            return select(pivotIndex + 1, high, k);
        }
    }

    return select(0, arr.length - 1, k);
}

const numbers = [3, 2, 1, 5, 6, 4];
console.log(quickSelect(numbers, 2)); // Output: 2 (2nd smallest element)

Time Complexity: Average case O(n), worst case O(n^2), where n is the length of the array.

6. Specialized Traversals

Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.

Example 17: Traversing a 2D array

Traversing 2D arrays (matrices) is a common operation in many algorithms.

function traverse2DArray(matrix) {
    const result = [];
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(traverse2DArray(matrix)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 18: Spiral Matrix Traversal

Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.

function spiralTraversal(matrix) {
    const result = [];
    if (matrix.length === 0) return result;

    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // Traverse right
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;

        // Traverse down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;

        if (top <= bottom) {
            // Traverse left
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse up
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

const matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
];
console.log(spiralTraversal(matrix));
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 19: Diagonal Traversal

Diagonal traversal of a matrix is another interesting pattern.

function diagonalTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];

    for (let d = 0; d < m + n - 1; d++) {
        const temp = [];
        for (let i = 0; i < m; i++) {
            const j = d - i;
            if (j >= 0 && j < n) {
                temp.push(matrix[i][j]);
            }
        }
        if (d % 2 === 0) {
            result.push(...temp.reverse());
        } else {
            result.push(...temp);
        }
    }

    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(diagonalTraversal(matrix));
// Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 20: Zigzag Traversal

Zigzag traversal is a pattern where we traverse the array in a zigzag manner.

function zigzagTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];
    let row = 0, col = 0;
    let goingDown = true;

    for (let i = 0; i < m * n; i++) {
        result.push(matrix[row][col]);

        if (goingDown) {
            if (row === m - 1 || col === 0) {
                goingDown = false;
                if (row === m - 1) {
                    col++;
                } else {
                    row++;
                }
            } else {
                row++;
                col--;
            }
        } else {
            if (col === n - 1 || row === 0) {
                goingDown = true;
                if (col === n - 1) {
                    row++;
                } else {
                    col++;
                }
            } else {
                row--;
                col++;
            }
        }
    }

    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(zigzagTraversal(matrix));
// Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

7. Performance Considerations

When working with array traversals, it's important to consider performance implications:

1. Time Complexity: Most basic traversals have O(n) time complexity, where n is the number of elements. However, nested loops or recursive calls can increase this to O(n^2) or higher.

2. Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.

3. Iterator Methods vs. For Loops: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.

4. Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.

5. Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.

6. Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.

7. Avoiding Array Resizing: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.

8. Problèmes de pratique de LeetCode

Pour renforcer davantage votre compréhension des techniques de traversée de tableaux, voici 15 problèmes LeetCode que vous pouvez pratiquer :

1. Deux sommes
2. Meilleur moment pour acheter et vendre des actions
3. Contient des doublons
4. Produit du tableau sauf soi
5. Sous-tableau maximum
6. Déplacer les zéros
7. 3Somme
8. Récipient contenant le plus d'eau
9. Faire pivoter le tableau
10. Trouver le minimum dans un tableau trié avec rotation
11. Recherche dans un tableau trié avec rotation
12. Fusionner les intervalles
13. Matrice spirale
14. Définir les zéros de la matrice
15. Séquence consécutive la plus longue

Ces problèmes couvrent un large éventail de techniques de traversée de tableaux et vous aideront à appliquer les concepts dont nous avons discuté dans cet article de blog.

9. Conclusion

La traversée de tableaux est une compétence fondamentale en programmation qui constitue la base de nombreux algorithmes et manipulations de données. Des boucles for de base aux techniques avancées telles que les fenêtres coulissantes et les parcours matriciels spécialisés, la maîtrise de ces méthodes améliorera considérablement votre capacité à résoudre efficacement des problèmes complexes.

Comme vous l'avez vu à travers ces 20 exemples, JavaScript propose un riche ensemble d'outils pour la traversée de tableaux, chacun avec ses propres atouts et cas d'utilisation. En comprenant quand et comment appliquer chaque technique, vous serez bien équipé pour relever un large éventail de défis de programmation.

N'oubliez pas que la clé pour devenir compétent est la pratique. Essayez d'implémenter ces méthodes de traversée dans vos propres projets et n'hésitez pas à explorer des techniques plus avancées à mesure que vous vous familiarisez avec les bases. Les problèmes LeetCode fournis vous donneront amplement l'occasion d'appliquer ces concepts dans divers scénarios.

À mesure que vous continuez à développer vos compétences, gardez toujours à l'esprit les implications en termes de performances de la méthode de traversée que vous avez choisie. Parfois, une simple boucle for peut être la solution la plus efficace, tandis que dans d'autres cas, une technique plus spécialisée comme la fenêtre coulissante ou la méthode à deux pointeurs pourrait être optimale.

Bon codage, et que vos tableaux soient toujours parcourus efficacement !

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!