陣列遍歷是資料結構和演算法（DSA）中每個開發人員都應該掌握的基本概念。在本綜合指南中，我們將探索在 JavaScript 中遍歷陣列的各種技術，從基本方法開始，逐步發展到更高階的方法。我們將涵蓋 20 個範例，範圍從簡單到高級，並包括 LeetCode 風格的問題來強化您的學習。
陣列遍歷是存取陣列中的每個元素來執行某種操作的過程。這是程式設計中的關鍵技能，構成了許多演算法和資料操作的基礎。在 JavaScript 中，陣列是通用的資料結構，提供多種方式來遍歷和操作資料。
我們先從陣列遍歷的基本方法開始。
經典的 for 迴圈是遍歷陣列最常見的方法之一。
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是陣列的長度。
filter 方法建立一個新數組，其中包含滿足特定條件的所有元素。
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是陣列的長度。
現在讓我們來探索一些陣列遍歷的中間技巧。
兩指針技術通常用於高效解決數組相關問題。
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.
為了進一步加深您對陣列遍歷技術的理解，您可以練習以下 15 個 LeetCode 問題：
這些問題涵蓋了廣泛的陣列遍歷技術，並將幫助您應用我們在本部落格文章中討論的概念。
陣列遍歷是程式設計中的基本技能，它構成了許多演算法和資料操作的基礎。從基本的 for 迴圈到滑動視窗和專門的矩陣遍歷等高級技術，掌握這些方法將顯著增強您高效解決複雜問題的能力。
正如您透過這 20 個範例所看到的，JavaScript 提供了一組豐富的陣列遍歷工具，每個工具都有自己的優勢和用例。透過了解何時以及如何應用每種技術，您將有能力應對各種程式設計挑戰。
記住，熟練的關鍵是練習。嘗試在您自己的專案中實現這些遍歷方法，當您對基礎知識越來越熟悉時，請毫不猶豫地探索更高級的技術。提供的 LeetCode 問題將為您提供充足的機會在各種場景中應用這些概念。
當您繼續發展自己的技能時，請務必牢記您選擇的遍歷方法對效能的影響。有時，簡單的 for 迴圈可能是最有效的解決方案，而在其他情況下，更專業的技術（如滑動視窗或兩個指標方法）可能是最佳的。
祝您編碼愉快，願您的陣列始終能夠有效率地遍歷！
以上是使用 JavaScript 在 DSA 中進行陣列遍歷：從基礎知識到進階技術的詳細內容。更多資訊請關注PHP中文網其他相關文章！
