Arrays sind grundlegende Datenstrukturen in der Informatik und werden häufig in verschiedenen Algorithmen und Problemlösungsszenarien verwendet. Dieser umfassende Leitfaden führt Sie durch die Grundlagen der Array-Manipulation in JavaScript und deckt Themen von der Grundstufe bis zur Fortgeschrittenenstufe ab. Wir werden Traversal, Einfügen, Löschen, Suchen und mehr sowie deren zeitliche Komplexität und praktische Beispiele untersuchen.
Ein Array ist eine Sammlung von Elementen, die an zusammenhängenden Speicherorten gespeichert sind. In JavaScript sind Arrays dynamisch und können Elemente unterschiedlichen Typs enthalten.
Grundlegende Array-Operationen:
// 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
Zeitkomplexität:
Traversal bedeutet, jedes Element des Arrays einmal zu besuchen. Es gibt mehrere Möglichkeiten, ein Array in JavaScript zu durchlaufen.
let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
Zeitkomplexität: O(n), wobei n die Anzahl der Elemente im Array ist.
let arr = [1, 2, 3, 4, 5]; arr.forEach(element => console.log(element));
Zeitkomplexität: O(n)
let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
console.log(element);
}
Zeitkomplexität: O(n)
Das Einfügen in Arrays kann am Anfang, am Ende oder an einer bestimmten Position erfolgen.
let arr = [1, 2, 3]; arr.push(4); console.log(arr); // Output: [1, 2, 3, 4]
Zeitkomplexität: O(1) (amortisiert)
let arr = [1, 2, 3]; arr.unshift(0); console.log(arr); // Output: [0, 1, 2, 3]
Zeitkomplexität: O(n), da alle vorhandenen Elemente verschoben werden müssen
let arr = [1, 2, 4, 5]; arr.splice(2, 0, 3); console.log(arr); // Output: [1, 2, 3, 4, 5]
Zeitkomplexität: O(n), da Elemente nach dem Einfügepunkt verschoben werden müssen
Ähnlich wie beim Einfügen kann das Löschen am Anfang, am Ende oder an einer bestimmten Position durchgeführt werden.
let arr = [1, 2, 3, 4]; arr.pop(); console.log(arr); // Output: [1, 2, 3]
Zeitkomplexität: O(1)
let arr = [1, 2, 3, 4]; arr.shift(); console.log(arr); // Output: [2, 3, 4]
Zeitkomplexität: O(n), da alle verbleibenden Elemente verschoben werden müssen
let arr = [1, 2, 3, 4, 5]; arr.splice(2, 1); console.log(arr); // Output: [1, 2, 4, 5]
Zeitkomplexität: O(n), da Elemente nach dem Löschpunkt verschoben werden müssen
Suchen ist ein häufiger Vorgang, der an Arrays durchgeführt wird. Schauen wir uns einige Suchtechniken an.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1
Zeitkomplexität: O(n)
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1
Zeitkomplexität: O(log n)
Lassen Sie uns nun einige fortgeschrittenere Techniken zur Array-Manipulation erkunden.
Die Zwei-Zeiger-Technik wird häufig verwendet, um Array-Probleme effizient zu lösen. Hier ist ein Beispiel für die Verwendung von zwei Zeigern zum direkten Umkehren eines Arrays:
function reverseArray(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
let arr = [1, 2, 3, 4, 5];
reverseArray(arr);
console.log(arr); // Output: [5, 4, 3, 2, 1]
Zeitkomplexität: O(n)
Die Schiebefenstertechnik ist nützlich zum Lösen von Subarray-Problemen. Hier ist ein Beispiel, um das maximale Summen-Subarray der Größe k zu finden:
function maxSumSubarray(arr, k) {
let maxSum = 0;
let windowSum = 0;
// Calculate sum of first window
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// Slide the window
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39
Zeitkomplexität: O(n)
Kadanes Algorithmus wird verwendet, um die maximale Subarray-Summe in einem Array zu ermitteln. Es ist ein Beispiel für dynamische Programmierung:
function kadane(arr) {
let maxSoFar = arr[0];
let maxEndingHere = arr[0];
for (let i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7
Zeitkomplexität: O(n)
Dieser Algorithmus wird verwendet, um ein Array zu sortieren, das nur Nullen, Einsen und Zweien enthält:
function dutchNationalFlag(arr) {
let low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] === 0) {
[arr[low], arr[mid]] = [arr[mid], arr[low]];
low++;
mid++;
} else if (arr[mid] === 1) {
mid++;
} else {
[arr[mid], arr[high]] = [arr[high], arr[mid]];
high--;
}
}
}
let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]
Zeitkomplexität: O(n)
Hier sind 50 Übungsaufgaben von leicht bis fortgeschritten. Einige davon stammen von LeetCode, während andere gängige Array-Manipulationsszenarien sind:
这里有 20 道 LeetCode 问题来测试你的数组操作技能：
通过解决这些问题并理解基本概念，您将显着提高 JavaScript 中数据结构和算法的数组操作技能。
请记住，掌握这些技术的关键是持续练习并理解解决方案的时间和空间复杂性。
编码愉快！
Das obige ist der detaillierte Inhalt vonBeherrschen der Array-Manipulation 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!
