数组是计算机科学中的基本数据结构，了解如何有效地操作它们对于任何开发人员都至关重要。在这篇博文中，我们将深入研究使用 JavaScript 的数组插入技术，涵盖从基础到高级的概念。我们将探索各种场景，提供 20 个示例，讨论时间复杂度，甚至解决一些 LeetCode 风格的问题。
数组是存储在连续内存位置的元素的集合。在 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
将元素插入数组的最简单方法是使用 push() 方法将其添加到末尾。
let numbers = [1, 2, 3]; numbers.push(4); console.log(numbers); // Output: [1, 2, 3, 4]
时间复杂度：O(1) - 常数时间
要在数组开头插入元素，请使用 unshift() 方法。
let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']
时间复杂度：O(n) - 线性时间，其中 n 是数组中的元素数量
扩展运算符可用于创建带有附加元素的新数组。
let animals = ['cat', 'dog']; let newAnimals = ['bird', ...animals, 'fish']; console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']
时间复杂度：O(n) - 线性时间，其中 n 是新数组中的元素总数
splice() 方法可用于在数组中的特定位置插入元素。
let fruits = ['apple', 'banana', 'orange']; fruits.splice(1, 0, 'mango'); console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']
时间复杂度：O(n) - 线性时间，其中 n 是插入点之后的元素数量
您可以使用 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 是插入点之后的元素数量
您还可以使用数组索引来覆盖特定位置的元素。
let letters = ['A', 'B', 'D', 'E']; letters[2] = 'C'; console.log(letters); // Output: ['A', 'B', 'C', 'E']
时间复杂度：O(1) - 常数时间
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 是所有数组中元素的总数
您可以使用带有展开运算符的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 是插入的元素数量
以下是如何将整个数组插入另一个数组的特定位置。
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 是结果数组中的元素总数
当您知道数组的最终大小时，预分配可以提高性能。
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) - 线性时间，但比动态增长数组更高效
对于大型数值数据数组，使用类型化数组会更高效。
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) - 线性时间，但对于数值数据具有更好的内存效率
插入多个元素时，批量插入比一次插入一个元素效率更高。
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) - 线性时间，但对于大量插入具有更好的性能
插入已排序数组时，我们可以使用二分查找来找到正确的位置。
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)
循环缓冲区是一个固定大小的环绕数组。这是循环缓冲区中插入的实现。
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
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
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
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
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
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
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)
Now that we've covered various insertion techniques, let's look at some LeetCode-style problems that involve array insertions.
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
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
To further test your understanding of array insertions, here are 15 LeetCode problems that involve various aspects of array manipulation and insertion:
These problems cover a wide range of difficulty levels and will help you practice various array insertion and manipulation techniques.
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中文网其他相关文章！
