JavaScript を使用した DSA の配列トラバーサル: 基本から高度なテクニックまで

配列トラバーサルは、すべての開発者が習得すべきデータ構造とアルゴリズム (DSA) の基本概念です。この包括的なガイドでは、基本的なアプローチから始めて、より高度な方法に進んで、JavaScript で配列を走査するためのさまざまなテクニックを検討します。簡単なレベルから上級レベルまでの 20 の例を取り上げ、学習を強化するための LeetCode スタイルの質問も含めます。

目次

1. 配列トラバーサルの概要
2. 基本的な配列の走査
   • 例 1: for ループの使用
   • 例 2: while ループの使用
   • 例 3: do-while ループの使用
   • 例 4: 逆走査
3. 最新の JavaScript 配列メソッド
   • 例 5: forEach メソッド
   • 例 6: マップメソッド
   • 例 7: フィルターメソッド
   • 例 8:reduce メソッド
4. 中級のトラバーステクニック
   • 例 9: 2 ポインター手法
   • 例 10: スライディング ウィンドウ
   • 例 11: Kadane のアルゴリズム
   • 例 12: オランダ国旗アルゴリズム
5. 高度なトラバーサル技術
   • 例 13: 再帰的走査
   • 例 14: ソートされた配列の二分探索
   • 例 15: ソートされた 2 つの配列をマージする
   • 例 16: クイック選択アルゴリズム
6. 特殊なトラバーサル
   • 例 17: 2D 配列の走査
   • 例 18: スパイラル行列トラバーサル
   • 例 19: 斜め移動
   • 例 20: ジグザグトラバーサル
7. パフォーマンスに関する考慮事項
8. LeetCode 練習問題
9. 結論

1. 配列トラバーサルの概要

配列トラバーサルは、配列内の各要素にアクセスして何らかの操作を実行するプロセスです。これはプログラミングにおける重要なスキルであり、多くのアルゴリズムやデータ操作の基礎を形成します。 JavaScript では、配列はデータを走査して操作するための複数の方法を提供する多用途のデータ構造です。

2. 基本的な配列の走査

配列トラバーサルの基本的な方法から始めましょう。

例 1: for ループの使用

古典的な for ループは、配列を走査する最も一般的な方法の 1 つです。

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

時間計算量: O(n)、n は配列の長さです。

例 2: while ループの使用

while ループは、特に終了条件がより複雑な場合、配列の走査にも使用できます。

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

時間計算量: 最悪の場合は O(n) ですが、負の数が早期に見つかった場合は小さくなる可能性があります。

例 3: do-while ループの使用

do-while ループは配列のトラバーサルではあまり一般的ではありませんが、特定のシナリオでは役立つ場合があります。

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

時間計算量: 最悪の場合は O(n) ですが、早期にゼロに遭遇した場合はそれより少なくなる可能性があります。

例 4: 逆走査

配列を逆順に走査することは、多くのアルゴリズムで一般的な操作です。

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]

時間計算量: O(n)、n は配列の長さです。

3. 最新の JavaScript 配列メソッド

ES6 以降のバージョンの JavaScript では、トラバーサルと操作を簡素化する強力な配列メソッドが導入されました。

例 5: forEach メソッド

forEach メソッドは、配列要素を反復処理するクリーンな方法を提供します。

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

時間計算量: O(n)、n は配列の長さです。

例 6: マップメソッド

map メソッドは、すべての要素に対して提供された関数を呼び出した結果を含む新しい配列を作成します。

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]

時間計算量: O(n)、n は配列の長さです。

例 7: フィルターメソッド

フィルター メソッドは、特定の条件を通過するすべての要素を含む新しい配列を作成します。

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]

時間計算量: O(n * sqrt(m))、n は配列の長さ、m は配列内の最大の数です。

例 8:reduce メソッド

reduce メソッドは、配列の各要素にリデューサ関数を適用し、単一の出力値を生成します。

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

時間計算量: O(n)、n は配列の長さです。

4. 中級のトラバーステクニック

次に、配列トラバーサルの中級テクニックをいくつか見てみましょう。

例 9: 2 ポインター手法

2 ポインター手法は、配列関連の問題を効率的に解決するためによく使用されます。

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. LeetCodeの練習問題

配列トラバーサル手法の理解をさらに深めるために、練習できる LeetCode の問題を 15 個紹介します。

1. 2つの合計
2. 株式を売買するのに最適な時期
3. 重複が含まれています
4. 自己を除く配列の積
5. 最大サブ配列
6. ゼロを移動
7. 3合計
8. ほとんどの水が入った容器
9. 配列を回転
10. 回転ソートされた配列の最小値を見つける
11. 回転ソート配列で検索
12. マージ間隔
13. スパイラルマトリックス
14. 行列のゼロを設定
15. 最長連続シーケンス

これらの問題は、配列トラバーサル手法の広範囲をカバーしており、このブログ投稿で説明した概念を適用するのに役立ちます。

9. 結論

配列トラバーサルは、多くのアルゴリズムやデータ操作の基礎を形成するプログラミングの基本的なスキルです。基本的な for ループから、スライディング ウィンドウや特殊な行列トラバーサルなどの高度なテクニックまで、これらのメソッドをマスターすると、複雑な問題を効率的に解決する能力が大幅に向上します。

これら 20 の例を通しておわかりのように、JavaScript は配列トラバーサルのための豊富なツール セットを提供しており、それぞれに独自の長所と使用例があります。各テクニックをいつどのように適用するかを理解することで、プログラミングの幅広い課題に対処する準備が整います。

熟練するための鍵は練習であることを忘れないでください。これらの走査メソッドを自分のプロジェクトに実装してみて、基本に慣れてきたら、躊躇せずにさらに高度なテクニックを試してみてください。提供される LeetCode の問題は、これらの概念をさまざまなシナリオに適用する十分な機会を提供します。

スキルを磨き続けるときは、選択した走査方法がパフォーマンスに与える影響を常に念頭に置いてください。単純な for ループが最も効率的なソリューションである場合もありますが、スライディング ウィンドウや 2 ポインター メソッドなどのより特殊なテクニックが最適な場合もあります。

コーディングを楽しんでください。配列が常に効率的に走査されますように!

以上がJavaScript を使用した DSA の配列トラバーサル: 基本から高度なテクニックまでの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。