使用 JavaScript 在 DSA 中插入数组：从基础到高级

数组是计算机科学中的基本数据结构，了解如何有效地操作它们对于任何开发人员都至关重要。在这篇博文中，我们将深入研究使用 JavaScript 的数组插入技术，涵盖从基础到高级的概念。我们将探索各种场景，提供 20 个示例，讨论时间复杂度，甚至解决一些 LeetCode 风格的问题。

目录

1. 数组简介
2. 基本数组插入
3. 插入特定位置
4. 插入多个元素
5. 高效的插入技术
6. 高级插入场景
7. LeetCode 风格的问题
8. 练习题

1. 数组简介

数组是存储在连续内存位置的元素的集合。在 JavaScript 中，数组是动态的，这意味着它们的大小可以增长或缩小。在我们深入研究插入技术之前，让我们快速回顾一下 JavaScript 数组的基础知识。

// Creating an array
let fruits = ['apple', 'banana', 'orange'];

// Accessing elements
console.log(fruits[0]); // Output: 'apple'

// Getting array length
console.log(fruits.length); // Output: 3

2. 基本数组插入

示例1：在末尾插入（push）

将元素插入数组的最简单方法是使用 push() 方法将其添加到末尾。

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

时间复杂度：O(1) - 常数时间

示例 2：在开头插入（unshift）

要在数组开头插入元素，请使用 unshift() 方法。

let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']

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

示例 3：使用扩展运算符插入

扩展运算符可用于创建带有附加元素的新数组。

let animals = ['cat', 'dog'];
let newAnimals = ['bird', ...animals, 'fish'];
console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']

时间复杂度：O(n) - 线性时间，其中 n 是新数组中的元素总数

3. 在特定位置插入

示例 4：使用 splice() 在特定索引处插入

splice() 方法可用于在数组中的特定位置插入元素。

let fruits = ['apple', 'banana', 'orange'];
fruits.splice(1, 0, 'mango');
console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']

时间复杂度：O(n) - 线性时间，其中 n 是插入点之后的元素数量

示例 5：使用 splice() 插入多个元素

您可以使用 splice() 一次插入多个元素。

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

时间复杂度：O(n) - 线性时间，其中 n 是插入点之后的元素数量

示例 6：覆盖元素

您还可以使用数组索引来覆盖特定位置的元素。

let letters = ['A', 'B', 'D', 'E'];
letters[2] = 'C';
console.log(letters); // Output: ['A', 'B', 'C', 'E']

时间复杂度：O(1) - 常数时间

4. 插入多个元素

示例 7：连接数组

concat() 方法可用于组合多个数组。

let arr1 = [1, 2];
let arr2 = [3, 4];
let arr3 = [5, 6];
let combined = arr1.concat(arr2, arr3);
console.log(combined); // Output: [1, 2, 3, 4, 5, 6]

时间复杂度：O(n) - 线性时间，其中 n 是所有数组中元素的总数

示例 8：将 Push() 与 Spread 运算符一起使用

您可以使用带有展开运算符的push()在末尾插入多个元素。

let numbers = [1, 2, 3];
let newNumbers = [4, 5, 6];
numbers.push(...newNumbers);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

时间复杂度：O(m) - 线性时间，其中 m 是插入的元素数量

示例 9：将一个数组插入另一个数组

以下是如何将整个数组插入另一个数组的特定位置。

function insertArray(mainArray, subArray, position) {
    return [...mainArray.slice(0, position), ...subArray, ...mainArray.slice(position)];
}

let main = [1, 2, 5, 6];
let sub = [3, 4];
console.log(insertArray(main, sub, 2)); // Output: [1, 2, 3, 4, 5, 6]

时间复杂度：O(n) - 线性时间，其中 n 是结果数组中的元素总数

5. 高效的插入技术

示例 10：预分配数组大小

当您知道数组的最终大小时，预分配可以提高性能。

function createSequence(n) {
    let arr = new Array(n);
    for (let i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    return arr;
}

console.log(createSequence(5)); // Output: [1, 2, 3, 4, 5]

时间复杂度：O(n) - 线性时间，但比动态增长数组更高效

示例 11：将类型化数组用于数值数据

对于大型数值数据数组，使用类型化数组会更高效。

let floatArray = new Float64Array(5);
for (let i = 0; i < 5; i++) {
    floatArray[i] = i * 1.1;
}
console.log(floatArray); // Output: Float64Array(5) [0, 1.1, 2.2, 3.3000000000000003, 4.4]

时间复杂度：O(n) - 线性时间，但对于数值数据具有更好的内存效率

示例 12：批量插入

插入多个元素时，批量插入比一次插入一个元素效率更高。

function batchInsert(arr, elements, batchSize = 1000) {
    for (let i = 0; i < elements.length; i += batchSize) {
        arr.push(...elements.slice(i, i + batchSize));
    }
    return arr;
}

let numbers = [1, 2, 3];
let newNumbers = Array.from({ length: 10000 }, (_, i) => i + 4);
console.log(batchInsert(numbers, newNumbers).length); // Output: 10003

时间复杂度：O(n) - 线性时间，但对于大量插入具有更好的性能

6. 高级插入场景

示例 13：插入已排序的数组

插入已排序数组时，我们可以使用二分查找来找到正确的位置。

function insertSorted(arr, element) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < element) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    arr.splice(left, 0, element);
    return arr;
}

let sortedArray = [1, 3, 5, 7, 9];
console.log(insertSorted(sortedArray, 4)); // Output: [1, 3, 4, 5, 7, 9]

时间复杂度：查找位置 O(log n) + 插入 O(n) = O(n)

示例 14：循环缓冲区插入

循环缓冲区是一个固定大小的环绕数组。这是循环缓冲区中插入的实现。

class CircularBuffer {
    constructor(size) {
        this.buffer = new Array(size);
        this.size = size;
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }

    insert(element) {
        this.buffer[this.tail] = element;
        this.tail = (this.tail + 1) % this.size;
        if (this.count < this.size) {
            this.count++;
        } else {
            this.head = (this.head + 1) % this.size;
        }
    }

    getBuffer() {
        return this.buffer.slice(this.head, this.head + this.count);
    }
}

let cb = new CircularBuffer(3);
cb.insert(1);
cb.insert(2);
cb.insert(3);
cb.insert(4);
console.log(cb.getBuffer()); // Output: [2, 3, 4]

Time Complexity: O(1) for insertion

Example 15: Sparse Array Insertion

Sparse arrays have "empty" slots. Here's how to work with them:

let sparseArray = new Array(5);
sparseArray[2] = 'Hello';
sparseArray[4] = 'World';
console.log(sparseArray); // Output: [empty × 2, 'Hello', empty, 'World']
console.log(sparseArray.length); // Output: 5

// Iterating over sparse array
sparseArray.forEach((item, index) => {
    if (item !== undefined) {
        console.log(`${index}: ${item}`);
    }
});
// Output:
// 2: Hello
// 4: World

Time Complexity: O(1) for insertion, O(n) for iteration

Example 16: Insertion with Deduplication

When inserting elements, you might want to avoid duplicates:

function insertUnique(arr, element) {
    if (!arr.includes(element)) {
        arr.push(element);
    }
    return arr;
}

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

Time Complexity: O(n) due to the includes check

Example 17: Insertion with Priority

Implementing a basic priority queue using an array:

class PriorityQueue {
    constructor() {
        this.queue = [];
    }

    insert(element, priority) {
        const item = { element, priority };
        let added = false;
        for (let i = 0; i < this.queue.length; i++) {
            if (item.priority < this.queue[i].priority) {
                this.queue.splice(i, 0, item);
                added = true;
                break;
            }
        }
        if (!added) {
            this.queue.push(item);
        }
    }

    getQueue() {
        return this.queue.map(item => item.element);
    }
}

let pq = new PriorityQueue();
pq.insert('Task 1', 2);
pq.insert('Task 2', 1);
pq.insert('Task 3', 3);
console.log(pq.getQueue()); // Output: ['Task 2', 'Task 1', 'Task 3']

Time Complexity: O(n) for insertion

Example 18: Dynamic 2D Array Insertion

Creating and inserting into a dynamic 2D array:

function create2DArray(rows, cols) {
    return Array.from({ length: rows }, () => new Array(cols).fill(0));
}

function insert2D(arr, row, col, value) {
    // Expand array if necessary
    while (arr.length <= row) {
        arr.push([]);
    }
    while (arr[row].length <= col) {
        arr[row].push(0);
    }
    arr[row][col] = value;
}

let matrix = create2DArray(2, 2);
insert2D(matrix, 1, 1, 5);
insert2D(matrix, 3, 3, 7);
console.log(matrix);
// Output: [
//   [0, 0],
//   [0, 5],
//   [0],
//   [0, 0, 0, 7]
// ]

Time Complexity: O(1) average case, O(n) worst case when expanding the array

Example 19: Insertion into a Trie (Prefix Tree)

While not strictly an array, a trie uses arrays (or objects) internally and is useful for string insertions:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.isEndOfWord = true;
    }

    search(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return current.isEndOfWord;
    }
}

let trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple")); // Output: true
console.log(trie.search("app")); // Output: true
console.log(trie.search("appl")); // Output: false

Time Complexity: O(m) for insertion and search, where m is the length of the word

Example 20: Insertion with Custom Sorting

Inserting elements while maintaining a custom sort order:

function insertSorted(arr, element, compareFn) {
    let index = arr.findIndex(item => compareFn(element, item) <= 0);
    if (index === -1) {
        arr.push(element);
    } else {
        arr.splice(index, 0, element);
    }
    return arr;
}

// Example: Sort by string length, then alphabetically
let words = ['cat', 'elephant', 'dog'];
let compareFn = (a, b) => {
    if (a.length !== b.length) {
        return a.length - b.length;
    }
    return a.localeCompare(b);
};

console.log(insertSorted(words, 'bear', compareFn));
// Output: ['cat', 'dog', 'bear', 'elephant']

Time Complexity: O(n) for finding the insertion point + O(n) for insertion = O(n)

7. LeetCode-Style Problems

Now that we've covered various insertion techniques, let's look at some LeetCode-style problems that involve array insertions.

Problem 1: Insert Interval

Given a sorted array of non-overlapping intervals and a new interval, insert the new interval and merge if necessary.

function insert(intervals, newInterval) {
    let result = [];
    let i = 0;

    // Add all intervals that come before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    // Add the merged interval
    result.push(newInterval);

    // Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

console.log(insert([[1,3],[6,9]], [2,5]));
// Output: [[1,5],[6,9]]

Time Complexity: O(n), where n is the number of intervals

Problem 2: Merge Sorted Array

Given two sorted arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;

merge(nums1, m, nums2, n);
console.log(nums1);
// Output: [1,2,2,3,5,6]

Time Complexity: O(m + n), where m and n are the lengths of nums1 and nums2 respectively

8. Practice Problems

To further test your understanding of array insertions, here are 15 LeetCode problems that involve various aspects of array manipulation and insertion:

1. Insert Interval
2. Merge Sorted Array
3. Insert Delete GetRandom O(1)
4. Search Insert Position
5. Array Partition I
6. Maximum Subarray
7. Move Zeroes
8. Sort Colors
9. Merge Intervals
10. Next Permutation
11. Find First and Last Position of Element in Sorted Array
12. 3Sum
13. Container With Most Water
14. Rotate Array
15. Product of Array Except Self

These problems cover a wide range of difficulty levels and will help you practice various array insertion and manipulation techniques.

Conclusion

Array insertion is a fundamental operation in data structures and algorithms. As we've seen, there are many ways to insert elements into arrays, each with its own use cases and time complexities. From simple push operations to more complex scenarios like maintaining sorted order or implementing data structures like circular buffers and tries, understanding these techniques will greatly enhance your ability to work with arrays efficiently.

Remember that the choice of insertion method can significantly impact the performance of your algorithm, especially when dealing with large datasets. Always consider the specific requirements of your problem and the trade-offs between time and space complexity when choosing an insertion technique.

Practice with the provided examples and LeetCode problems to solidify your understanding and improve your problem-solving skills.

Happy coding!

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