使用 JavaScript 在 DSA 中插入陣列：從基礎到高級
- WBOY原創
- 2024-09-03 21:05:01431瀏覽
陣列是電腦科學中的基本資料結構，了解如何有效地操作它們對於任何開發人員都至關重要。在這篇文章中，我們將深入研究使用 JavaScript 的陣列插入技術，涵蓋從基礎到進階的概念。我們將探索各種場景，提供 20 個範例，討論時間複雜度，甚至解決一些 LeetCode 風格的問題。
目錄
- 陣列簡介
- 基本數組插入
- 插入特定位置
- 插入多個元素
- 高效率的插入技術
- 進階插入場景
- LeetCode 風格的問題
- 練習題
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:
- Insert Interval
- Merge Sorted Array
- Insert Delete GetRandom O(1)
- Search Insert Position
- Array Partition I
- Maximum Subarray
- Move Zeroes
- Sort Colors
- Merge Intervals
- Next Permutation
- Find First and Last Position of Element in Sorted Array
- 3Sum
- Container With Most Water
- Rotate Array
- 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中文網其他相關文章！