使用 JavaScript 掌握 DSA 中的数组操作：从基础到高级

掌握 DSA JavaScript 中的数组操作

数组是计算机科学中的基本数据结构，广泛应用于各种算法和问题解决场景中。这份综合指南将带您了解 JavaScript 中数组操作的基础知识，涵盖从基础到高级的主题。我们将探索遍历、插入、删除、搜索等，以及它们的时间复杂度和实际示例。

目录

1. 数组简介
2. 数组遍历
3. 插入数组
4. 数组中的删除
5. 在数组中搜索
6. 高级数组操作技术
7. 练习题
8. LeetCode 问题链接

1. 数组简介

数组是存储在连续内存位置的元素的集合。在 JavaScript 中，数组是动态的，可以保存不同类型的元素。

基本数组操作：

// Creating an array
let arr = [1, 2, 3, 4, 5];

// Accessing elements
console.log(arr[0]); // Output: 1

// Modifying elements
arr[2] = 10;
console.log(arr); // Output: [1, 2, 10, 4, 5]

// Getting array length
console.log(arr.length); // Output: 5

时间复杂度：

• 访问元素：O(1)
• 修改元素：O(1)
• 获取数组长度：O(1)

2. 数组遍历

遍历意味着访问数组的每个元素一次。在 JavaScript 中，有多种方法可以遍历数组。

2.1 使用for循环

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

时间复杂度：O(n)，其中 n 是数组中元素的数量。

2.2 使用forEach

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

时间复杂度：O(n)

2.3 使用for...of循环

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

时间复杂度：O(n)

3. 数组中的插入

可以在数组的开头、结尾或特定位置插入。

3.1 末尾插入

let arr = [1, 2, 3];
arr.push(4);
console.log(arr); // Output: [1, 2, 3, 4]

时间复杂度：O(1)（摊销）

3.2 在开头插入

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

时间复杂度：O(n)，因为所有现有元素都需要移动

3.3 在特定位置插入

let arr = [1, 2, 4, 5];
arr.splice(2, 0, 3);
console.log(arr); // Output: [1, 2, 3, 4, 5]

时间复杂度：O(n)，因为插入点之后的元素需要移动

4. 数组中的删除

与插入类似，删除可以在开头、结尾或特定位置进行。

4.1 从末尾删除

let arr = [1, 2, 3, 4];
arr.pop();
console.log(arr); // Output: [1, 2, 3]

时间复杂度：O(1)

4.2 从头删除

let arr = [1, 2, 3, 4];
arr.shift();
console.log(arr); // Output: [2, 3, 4]

时间复杂度：O(n)，因为所有剩余元素都需要移位

4.3 特定位置的删除

let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
console.log(arr); // Output: [1, 2, 4, 5]

时间复杂度：O(n)，因为删除点之后的元素需要移位

5. 在数组中搜索

搜索是对数组执行的常见操作。让我们看看一些搜索技巧。

5.1 线性搜索

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1

时间复杂度：O(n)

5.2 二分查找（对于排序数组）

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1

时间复杂度：O(log n)

6. 先进的数组操作技术

现在让我们探索一些更高级的数组操作技术。

6.1 两指针技术

两指针技术经常被用来有效地解决数组问题。这是使用两个指针就地反转数组的示例：

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

let arr = [1, 2, 3, 4, 5];
reverseArray(arr);
console.log(arr); // Output: [5, 4, 3, 2, 1]

时间复杂度：O(n)

6.2 滑动窗口技术

滑动窗口技术对于解决子数组问题很有用。下面是一个查找大小为 k 的最大和子数组的示例：

function maxSumSubarray(arr, k) {
    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;
}

let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39

时间复杂度：O(n)

6.3 Kadane算法

Kadane 算法用于查找数组中的最大子数组和。这是动态规划的一个例子：

function kadane(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;
}

let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7

时间复杂度：O(n)

6.4 荷兰国旗算法

该算法用于对仅包含 0、1 和 2 的数组进行排序：

function dutchNationalFlag(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--;
        }
    }
}

let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]

时间复杂度：O(n)

7. 练习题

这里有 50 个练习题，从简单到高级。其中一些来自 LeetCode，而另一些则是常见的数组操作场景：

1. Sum all elements in an array
2. Find the maximum element in an array
3. Reverse an array in-place
4. Remove duplicates from a sorted array
5. Rotate an array by k steps
6. Find the second largest element in an array
7. Merge two sorted arrays
8. Find the missing number in an array of 1 to n
9. Move all zeros to the end of the array
10. Find the intersection of two arrays
11. Find the union of two arrays
12. Check if an array is a subset of another array
13. Find the equilibrium index in an array
14. Rearrange positive and negative numbers in an array
15. Find the majority element in an array
16. Find the peak element in an array
17. Implement a circular array
18. Find the smallest positive missing number in an array
19. Trapping Rain Water problem
20. Implement a stack using an array
21. Implement a queue using an array
22. Find the longest increasing subsequence
23. Implement binary search in a rotated sorted array
24. Find the maximum sum of a subarray of size k
25. Implement the Kadane's algorithm
26. Find the minimum number of platforms required for a railway station
27. Find the longest subarray with equal number of 0s and 1s
28. Implement the Dutch National Flag algorithm
29. Find the smallest subarray with sum greater than a given value
30. Implement the Boyer-Moore Majority Voting algorithm
31. Find the maximum product subarray
32. Implement the Jump Game algorithm
33. Find the next greater element for every element in an array
34. Implement the Sliding Window Maximum algorithm
35. Find the longest substring without repeating characters
36. Implement the Merge Intervals algorithm
37. Find the minimum number of jumps to reach the end of an array
38. Implement the Stock Buy Sell to Maximize Profit algorithm
39. Find the Longest Palindromic Substring
40. Implement the Longest Common Subsequence algorithm
41. Find the Shortest Unsorted Continuous Subarray
42. Implement the Container With Most Water algorithm
43. Find the Longest Consecutive Sequence in an array
44. Implement the Maximum Product of Three Numbers algorithm
45. Find the Kth Largest Element in an Array
46. Implement the Find All Duplicates in an Array algorithm
47. Find the Minimum Size Subarray Sum
48. Implement the Product of Array Except Self algorithm
49. Find the Maximum Gap in a sorted array
50. Implement the Median of Two Sorted Arrays algorithm

8. LeetCode Problem Links

Here are 20 LeetCode problems to test your array manipulation skills:

1. Two Sum
2. Best Time to Buy and Sell Stock
3. Contains Duplicate
4. Product of Array Except Self
5. Maximum Subarray
6. Merge Intervals
7. 3Sum
8. Container With Most Water
9. Rotate Array
10. Search in Rotated Sorted Array
11. Find Minimum in Rotated Sorted Array
12. Next Permutation
13. Subarray Sum Equals K
14. Spiral Matrix
15. Jump Game
16. Longest Consecutive Sequence
17. Find All Duplicates in an Array
18. Kth Largest Element in an Array
19. Trapping Rain Water
20. Median of Two Sorted Arrays

By working through these problems and understanding the underlying concepts, you'll significantly improve your array manipulation skills in JavaScript for Data Structures and Algorithms.

Remember, the key to mastering these techniques is consistent practice and understanding the time and space complexities of your solutions.

Happy coding!

以上是使用 JavaScript 掌握 DSA 中的数组操作：从基础到高级的详细内容。更多信息请关注PHP中文网其他相关文章！