Arrays sind grundlegende Datenstrukturen in der Informatik, und das Verständnis, wie man sie effizient manipuliert, ist für jeden Entwickler von entscheidender Bedeutung. In diesem Blogbeitrag werden wir uns eingehend mit Techniken zum Einfügen von Arrays mithilfe von JavaScript befassen und dabei Konzepte von der Grundstufe bis zur fortgeschrittenen Ebene abdecken. Wir werden verschiedene Szenarien untersuchen, 20 Beispiele bereitstellen, zeitliche Komplexitäten diskutieren und sogar einige Probleme im LeetCode-Stil angehen.
Ein Array ist eine Sammlung von Elementen, die an zusammenhängenden Speicherorten gespeichert sind. In JavaScript sind Arrays dynamisch, das heißt, sie können größer oder kleiner werden. Bevor wir uns mit Einfügetechniken befassen, lassen Sie uns kurz die Grundlagen von JavaScript-Arrays zusammenfassen.
// 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
Der einfachste Weg, ein Element in ein Array einzufügen, besteht darin, es am Ende mit der push()-Methode hinzuzufügen.
let numbers = [1, 2, 3]; numbers.push(4); console.log(numbers); // Output: [1, 2, 3, 4]
Zeitkomplexität: O(1) – Konstante Zeit
Um ein Element am Anfang eines Arrays einzufügen, verwenden Sie die Methode unshift().
let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Anzahl der Elemente im Array ist
Der Spread-Operator kann verwendet werden, um ein neues Array mit zusätzlichen Elementen zu erstellen.
let animals = ['cat', 'dog']; let newAnimals = ['bird', ...animals, 'fish']; console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Gesamtzahl der Elemente im neuen Array ist
Mit der splice()-Methode können Elemente an einer bestimmten Position im Array eingefügt werden.
let fruits = ['apple', 'banana', 'orange']; fruits.splice(1, 0, 'mango'); console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Anzahl der Elemente nach dem Einfügepunkt ist
Mit splice() können Sie mehrere Elemente gleichzeitig einfügen.
let numbers = [1, 2, 5, 6]; numbers.splice(2, 0, 3, 4); console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Anzahl der Elemente nach dem Einfügepunkt ist
Sie können die Array-Indizierung auch verwenden, um Elemente an bestimmten Positionen zu überschreiben.
let letters = ['A', 'B', 'D', 'E']; letters[2] = 'C'; console.log(letters); // Output: ['A', 'B', 'C', 'E']
Zeitkomplexität: O(1) – Konstante Zeit
Die concat()-Methode kann verwendet werden, um mehrere Arrays zu kombinieren.
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]
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Gesamtzahl der Elemente in allen Arrays ist
Sie können push() mit dem Spread-Operator verwenden, um am Ende mehrere Elemente einzufügen.
let numbers = [1, 2, 3]; let newNumbers = [4, 5, 6]; numbers.push(...newNumbers); console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]
Zeitkomplexität: O(m) – Lineare Zeit, wobei m die Anzahl der eingefügten Elemente ist
So können Sie ein ganzes Array an einer bestimmten Position in ein anderes einfügen.
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]
Zeitkomplexität: O(n) – Lineare Zeit, wobei n die Gesamtzahl der Elemente im resultierenden Array ist
Wenn Sie die endgültige Größe des Arrays kennen, kann die Vorabzuweisung die Leistung verbessern.
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]
Zeitkomplexität: O(n) – Lineare Zeit, aber effizienter als das dynamische Erweitern des Arrays
Bei großen Arrays numerischer Daten kann die Verwendung typisierter Arrays effizienter sein.
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]
Zeitkomplexität: O(n) – Lineare Zeit, aber mit besserer Speichereffizienz für numerische Daten
Beim Einfügen mehrerer Elemente kann es effizienter sein, dies in Stapeln zu tun als einzeln.
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
Zeitkomplexität: O(n) – Lineare Zeit, aber mit besserer Leistung für große Einfügungen
Beim Einfügen in ein sortiertes Array können wir die binäre Suche verwenden, um die richtige Position zu finden.
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]
Zeitkomplexität: O(log n) zum Finden der Position + O(n) zum Einfügen = O(n)
Ein Ringpuffer ist ein Array fester Größe, das sich umschließt. Hier ist eine Implementierung der Einfügung in einen Ringpuffer.
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!
Das obige ist der detaillierte Inhalt vonArray-Einfügung in DSA mit JavaScript: Von den Grundlagen bis zu Fortgeschrittenen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
