JavaScript を使用した DSA での配列操作のマスター: 基本から上級まで-jsチュートリアル-php.cn

Mastering Array Manipulation in DSA using JavaScript: From Basics to Advanced

DSA 用の JavaScript での配列操作をマスターする

配列はコンピューターサイエンスにおける基本的なデータ構造であり、さまざまなアルゴリズムや問題解決シナリオで広く使用されています。この包括的なガイドでは、基本レベルから高度なレベルまでのトピックをカバーし、JavaScript での配列操作の基本を説明します。走査、挿入、削除、検索などを、時間計算量や実際の例とともに説明します。

1. 配列の概要

配列は、連続したメモリ位置に格納される要素のコレクションです。 JavaScript では、配列は動的であり、さまざまな型の要素を保持できます。

基本的な配列操作:

// 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

ログイン後にコピー

時間計算量:

要素へのアクセス: O(1)
要素の変更: O(1)
配列の長さの取得: O(1)

2. 配列トラバーサル

トラバーサルとは、配列の各要素を 1 回ずつ訪問することを意味します。 JavaScript で配列を走査するにはいくつかの方法があります。

2.1 for ループの使用

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

ログイン後にコピー

時間計算量: O(n)、n は配列内の要素の数です。

2.2 forEachの使用

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

ログイン後にコピー

時間計算量: O(n)

2.3 for...of ループの使用

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

ログイン後にコピー

時間計算量: O(n)

3. 配列への挿入

配列への挿入は、先頭、末尾、または特定の位置で行うことができます。

3.1 最後に挿入

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

ログイン後にコピー

時間計算量: O(1) (償却)

3.2 先頭への挿入

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

ログイン後にコピー

時間計算量: O(n)、既存のすべての要素をシフトする必要があるため

3.3 特定の位置への挿入

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

ログイン後にコピー

時間計算量: O(n)、挿入ポイントの後の要素をシフトする必要があるため

4. 配列内の削除

挿入と同様に、削除も先頭、末尾、または特定の位置で実行できます。

4.1 末尾からの削除

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

ログイン後にコピー

時間計算量: O(1)

4.2 先頭から削除

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

ログイン後にコピー

時間計算量: O(n)、残りの要素はすべてシフトする必要があるため

4.3 特定の位置の削除

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

ログイン後にコピー

時間計算量: O(n)、削除ポイント以降の要素をシフトする必要があるため

5. 配列内の検索

検索は配列に対して実行される一般的な操作です。いくつかの検索テクニックを見てみましょう。

5.1 線形探索

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

ログイン後にコピー

時間計算量: O(n)

5.2 二分探索 (ソートされた配列の場合)

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

ログイン後にコピー

時間計算量: O(log n)

6. 高度な配列操作テクニック

次に、配列操作のためのより高度なテクニックをいくつか見てみましょう。

6.1 ツーポインタ技術

2 ポインター手法は、配列の問題を効率的に解決するためによく使用されます。次に、2 つのポインターを使用して配列をその場で反転する例を示します。

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]

ログイン後にコピー

時間計算量: O(n)

6.2 スライディングウィンドウ手法

スライディングウィンドウ手法は、部分配列の問題を解決するのに役立ちます。サイズ k の最大合計部分配列を見つける例を次に示します:

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

ログイン後にコピー

時間計算量: O(n)

6.3 カダネのアルゴリズム

Kadane のアルゴリズムは、配列内の最大部分配列合計を見つけるために使用されます。これは動的プログラミングの例です:

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

ログイン後にコピー

時間計算量: O(n)

6.4 オランダ国旗アルゴリズム

このアルゴリズムは、0、1、2 のみを含む配列をソートするために使用されます:

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]

ログイン後にコピー

時間計算量: O(n)