配列トラバーサルは、すべての開発者が習得すべきデータ構造とアルゴリズム (DSA) の基本概念です。この包括的なガイドでは、基本的なアプローチから始めて、より高度な方法に進んで、JavaScript で配列を走査するためのさまざまなテクニックを検討します。簡単なレベルから上級レベルまでの 20 の例を取り上げ、学習を強化するための LeetCode スタイルの質問も含めます。
配列トラバーサルは、配列内の各要素にアクセスして何らかの操作を実行するプロセスです。これはプログラミングにおける重要なスキルであり、多くのアルゴリズムやデータ操作の基礎を形成します。 JavaScript では、配列はデータを走査して操作するための複数の方法を提供する多用途のデータ構造です。
配列トラバーサルの基本的な方法から始めましょう。
古典的な 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 は配列の長さです。
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) ですが、負の数が早期に見つかった場合は小さくなる可能性があります。
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) ですが、早期にゼロに遭遇した場合はそれより少なくなる可能性があります。
配列を逆順に走査することは、多くのアルゴリズムで一般的な操作です。
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 は配列の長さです。
ES6 以降のバージョンの JavaScript では、トラバーサルと操作を簡素化する強力な配列メソッドが導入されました。
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 は配列の長さです。
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 は配列の長さです。
フィルター メソッドは、特定の条件を通過するすべての要素を含む新しい配列を作成します。
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 は配列内の最大の数です。
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 は配列の長さです。
次に、配列トラバーサルの中級テクニックをいくつか見てみましょう。
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.
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.
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.
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.
Let's explore some more advanced techniques for array 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.
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.
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.
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.
Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.
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.
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.
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.
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.
When working with array traversals, it's important to consider performance implications:
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.
Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.
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.
Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.
Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.
Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.
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.
配列トラバーサル手法の理解をさらに深めるために、練習できる LeetCode の問題を 15 個紹介します。
これらの問題は、配列トラバーサル手法の広範囲をカバーしており、このブログ投稿で説明した概念を適用するのに役立ちます。
配列トラバーサルは、多くのアルゴリズムやデータ操作の基礎を形成するプログラミングの基本的なスキルです。基本的な for ループから、スライディング ウィンドウや特殊な行列トラバーサルなどの高度なテクニックまで、これらのメソッドをマスターすると、複雑な問題を効率的に解決する能力が大幅に向上します。
これら 20 の例を通しておわかりのように、JavaScript は配列トラバーサルのための豊富なツール セットを提供しており、それぞれに独自の長所と使用例があります。各テクニックをいつどのように適用するかを理解することで、プログラミングの幅広い課題に対処する準備が整います。
熟練するための鍵は練習であることを忘れないでください。これらの走査メソッドを自分のプロジェクトに実装してみて、基本に慣れてきたら、躊躇せずにさらに高度なテクニックを試してみてください。提供される LeetCode の問題は、これらの概念をさまざまなシナリオに適用する十分な機会を提供します。
スキルを磨き続けるときは、選択した走査方法がパフォーマンスに与える影響を常に念頭に置いてください。単純な for ループが最も効率的なソリューションである場合もありますが、スライディング ウィンドウや 2 ポインター メソッドなどのより特殊なテクニックが最適な場合もあります。
コーディングを楽しんでください。配列が常に効率的に走査されますように!
以上がJavaScript を使用した DSA の配列トラバーサル: 基本から高度なテクニックまでの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
