数组遍历是数据结构和算法（DSA）中的一个基本概念，每个开发人员都应该掌握。在本综合指南中，我们将探索在 JavaScript 中遍历数组的各种技术，从基本方法开始，逐步发展到更高级的方法。我们将涵盖 20 个示例，范围从简单到高级，并包括 LeetCode 风格的问题来强化您的学习。
目录
- 数组遍历简介
-
基本数组遍历
- 示例 1：使用 for 循环
- 示例 2：使用 while 循环
- 示例 3：使用 do-while 循环
- 示例4：反向遍历
-
现代 JavaScript 数组方法
- 示例 5：forEach 方法
- 示例6：map方法
- 示例7：过滤方法
- 示例8：reduce方法
-
中级遍历技术
- 示例9：两指针技术
- 示例10：滑动窗口
- 示例 11：Kadane 算法
- 示例12：荷兰国旗算法
-
高级遍历技术
- 示例13：递归遍历
- 示例 14：排序数组上的二分搜索
- 示例 15：合并两个排序数组
- 示例 16：快速选择算法
-
专门的遍历
- 示例 17：遍历 2D 数组
- 示例 18：螺旋矩阵遍历
- 示例 19：对角线遍历
- 示例 20：之字形遍历
- 性能考虑因素
- LeetCode 练习题
- 结论
1. 数组遍历简介
数组遍历是访问数组中的每个元素来执行某种操作的过程。这是编程中的一项关键技能，构成了许多算法和数据操作的基础。在 JavaScript 中，数组是通用的数据结构，提供多种方式来遍历和操作数据。
2. 基本数组遍历
我们先从数组遍历的基本方法开始。
示例 1：使用 for 循环
经典的 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是数组的长度。
示例 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方法
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：过滤法
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是数组中最大的数字。
示例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：两指针技术
两指针技术通常用于高效解决数组相关问题。
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:
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.
8.LeetCode练习题
为了进一步加深您对数组遍历技术的理解，您可以练习以下 15 个 LeetCode 问题：
- 两和
- 买卖股票的最佳时机
- 包含重复
- 除自身之外的数组的乘积
- 最大子数组
- 移动零
- 3Sum
- 装最多水的容器
- 旋转数组
- 查找旋转排序数组中的最小值
- 在旋转排序数组中搜索
- 合并间隔
- 螺旋矩阵
- 设置矩阵零
- 最长连续序列
这些问题涵盖了广泛的数组遍历技术，并将帮助您应用我们在本博文中讨论的概念。
9. 结论
数组遍历是编程中的一项基本技能，它构成了许多算法和数据操作的基础。从基本的 for 循环到滑动窗口和专门的矩阵遍历等高级技术，掌握这些方法将显着增强您高效解决复杂问题的能力。
正如您通过这 20 个示例所看到的，JavaScript 提供了一组丰富的数组遍历工具，每个工具都有自己的优势和用例。通过了解何时以及如何应用每种技术，您将有能力应对各种编程挑战。
记住，熟练的关键是练习。尝试在您自己的项目中实现这些遍历方法，当您对基础知识越来越熟悉时，请毫不犹豫地探索更高级的技术。提供的 LeetCode 问题将为您提供充足的机会在各种场景中应用这些概念。
当您继续发展自己的技能时，请始终牢记您选择的遍历方法对性能的影响。有时，简单的 for 循环可能是最有效的解决方案，而在其他情况下，更专业的技术（例如滑动窗口或两指针方法）可能是最佳的。
祝您编码愉快，愿您的数组始终能够高效地遍历！
以上是使用 JavaScript 在 DSA 中进行数组遍历：从基础知识到高级技术的详细内容。更多信息请关注PHP中文网其他相关文章！
