使用 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 



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

<h3>
  
  
  2.2 使用forEach
</h3>



<pre class="brush:php;toolbar:false">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 



<p>时间复杂度：O(n)</p>

<h3>
  
  
  5.2 二分查找（对于排序数组）
</h3>



<pre class="brush:php;toolbar:false">function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left 



<p>时间复杂度：O(log n)</p>

<h2>
  
  
  6. 先进的数组操作技术
</h2>

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

<h3>
  
  
  6.1 两指针技术
</h3>

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

<pre class="brush:php;toolbar:false">function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left 



<p>时间复杂度：O(n)</p>

<h3>
  
  
  6.2 滑动窗口技术
</h3>

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

<pre class="brush:php;toolbar:false">function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i 



<p>时间复杂度：O(n)</p>

<h3>
  
  
  6.3 Kadane算法
</h3>

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

<pre class="brush:php;toolbar:false">function kadane(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i 



<p>时间复杂度：O(n)</p>

<h3>
  
  
  6.4 荷兰国旗算法
</h3>

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

<pre class="brush:php;toolbar:false">function dutchNationalFlag(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid 



<p>时间复杂度：O(n)</p>

<h2>
  
  
  7. 练习题
</h2>

<p>这里有 50 个练习题，从简单到高级。其中一些来自 LeetCode，而另一些则是常见的数组操作场景：</p><ol>
<li>Sum all elements in an array</li>
<li>Find the maximum element in an array</li>
<li>Reverse an array in-place</li>
<li>Remove duplicates from a sorted array</li>
<li>Rotate an array by k steps</li>
<li>Find the second largest element in an array</li>
<li>Merge two sorted arrays</li>
<li>Find the missing number in an array of 1 to n</li>
<li>Move all zeros to the end of the array</li>
<li>Find the intersection of two arrays</li>
<li>Find the union of two arrays</li>
<li>Check if an array is a subset of another array</li>
<li>Find the equilibrium index in an array</li>
<li>Rearrange positive and negative numbers in an array</li>
<li>Find the majority element in an array</li>
<li>Find the peak element in an array</li>
<li>Implement a circular array</li>
<li>Find the smallest positive missing number in an array</li>
<li>Trapping Rain Water problem</li>
<li>Implement a stack using an array</li>
<li>Implement a queue using an array</li>
<li>Find the longest increasing subsequence</li>
<li>Implement binary search in a rotated sorted array</li>
<li>Find the maximum sum of a subarray of size k</li>
<li>Implement the Kadane's algorithm</li>
<li>Find the minimum number of platforms required for a railway station</li>
<li>Find the longest subarray with equal number of 0s and 1s</li>
<li>Implement the Dutch National Flag algorithm</li>
<li>Find the smallest subarray with sum greater than a given value</li>
<li>Implement the Boyer-Moore Majority Voting algorithm</li>
<li>Find the maximum product subarray</li>
<li>Implement the Jump Game algorithm</li>
<li>Find the next greater element for every element in an array</li>
<li>Implement the Sliding Window Maximum algorithm</li>
<li>Find the longest substring without repeating characters</li>
<li>Implement the Merge Intervals algorithm</li>
<li>Find the minimum number of jumps to reach the end of an array</li>
<li>Implement the Stock Buy Sell to Maximize Profit algorithm</li>
<li>Find the Longest Palindromic Substring</li>
<li>Implement the Longest Common Subsequence algorithm</li>
<li>Find the Shortest Unsorted Continuous Subarray</li>
<li>Implement the Container With Most Water algorithm</li>
<li>Find the Longest Consecutive Sequence in an array</li>
<li>Implement the Maximum Product of Three Numbers algorithm</li>
<li>Find the Kth Largest Element in an Array</li>
<li>Implement the Find All Duplicates in an Array algorithm</li>
<li>Find the Minimum Size Subarray Sum</li>
<li>Implement the Product of Array Except Self algorithm</li>
<li>Find the Maximum Gap in a sorted array</li>
<li>Implement the Median of Two Sorted Arrays algorithm</li>
</ol>

<h2>
  
  
  8. LeetCode Problem Links
</h2>

<p>Here are 20 LeetCode problems to test your array manipulation skills:</p>

<ol>
<li>Two Sum</li>
<li>Best Time to Buy and Sell Stock</li>
<li>Contains Duplicate</li>
<li>Product of Array Except Self</li>
<li>Maximum Subarray</li>
<li>Merge Intervals</li>
<li>3Sum</li>
<li>Container With Most Water</li>
<li>Rotate Array</li>
<li>Search in Rotated Sorted Array</li>
<li>Find Minimum in Rotated Sorted Array</li>
<li>Next Permutation</li>
<li>Subarray Sum Equals K</li>
<li>Spiral Matrix</li>
<li>Jump Game</li>
<li>Longest Consecutive Sequence</li>
<li>Find All Duplicates in an Array</li>
<li>Kth Largest Element in an Array</li>
<li>Trapping Rain Water</li>
<li>Median of Two Sorted Arrays</li>
</ol>

<p>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.</p>

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

<p>Happy coding!</p>


          

            
        

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