Sisipan Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan

Array ialah struktur data asas dalam sains komputer dan memahami cara memanipulasinya dengan cekap adalah penting bagi mana-mana pembangun. Dalam catatan blog ini, kami akan menyelami teknik sisipan tatasusunan menggunakan JavaScript, merangkumi konsep daripada peringkat asas hingga lanjutan. Kami akan meneroka pelbagai senario, memberikan 20 contoh, membincangkan kerumitan masa dan juga menangani beberapa masalah gaya LeetCode.

Jadual Kandungan

1. Pengenalan kepada Tatasusunan
2. Sisipan Tatasusunan Asas
3. Memasukkan pada Kedudukan Tertentu
4. Memasukkan Pelbagai Elemen
5. Teknik Sisipan Yang Cekap
6. Senario Sisipan Terperinci
7. Masalah Gaya LeetCode
8. Masalah Amalan

1. Pengenalan kepada Tatasusunan

Susun atur ialah koleksi elemen yang disimpan di lokasi memori bersebelahan. Dalam JavaScript, tatasusunan adalah dinamik, bermakna ia boleh membesar atau mengecil dalam saiz. Sebelum kita menyelami teknik sisipan, mari kita ringkaskan semula asas tatasusunan JavaScript dengan cepat.

// 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. Sisipan Tatasusunan Asas

Contoh 1: Memasukkan di Hujung (tolak)

Cara paling mudah untuk memasukkan elemen ke dalam tatasusunan ialah menambahkannya pada penghujung menggunakan kaedah push().

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

Kerumitan Masa: O(1) - Masa malar

Contoh 2: Memasukkan pada Permulaan (nyah anjakan)

Untuk memasukkan elemen pada permulaan tatasusunan, gunakan kaedah unshift().

let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']

Kerumitan Masa: O(n) - Masa linear, dengan n ialah bilangan elemen dalam tatasusunan

Contoh 3: Memasukkan Menggunakan Operator Spread

Pengendali hamparan boleh digunakan untuk mencipta tatasusunan baharu dengan elemen tambahan.

let animals = ['cat', 'dog'];
let newAnimals = ['bird', ...animals, 'fish'];
console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']

Kerumitan Masa: O(n) - Masa linear, dengan n ialah jumlah bilangan elemen dalam tatasusunan baharu

3. Memasukkan pada Kedudukan Tertentu

Contoh 4: Menggunakan splice() untuk Memasukkan pada Indeks Tertentu

Kaedah splice() boleh digunakan untuk memasukkan elemen pada kedudukan tertentu dalam tatasusunan.

let fruits = ['apple', 'banana', 'orange'];
fruits.splice(1, 0, 'mango');
console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']

Kerumitan Masa: O(n) - Masa linear, dengan n ialah bilangan elemen selepas titik sisipan

Contoh 5: Memasukkan Berbilang Elemen dengan splice()

Anda boleh memasukkan berbilang elemen serentak menggunakan splice().

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

Kerumitan Masa: O(n) - Masa linear, dengan n ialah bilangan elemen selepas titik sisipan

Contoh 6: Mengganti Elemen

Anda juga boleh menggunakan pengindeksan tatasusunan untuk menulis ganti elemen pada kedudukan tertentu.

let letters = ['A', 'B', 'D', 'E'];
letters[2] = 'C';
console.log(letters); // Output: ['A', 'B', 'C', 'E']

Kerumitan Masa: O(1) - Masa malar

4. Memasukkan Pelbagai Elemen

Contoh 7: Susunan Bercantum

Kaedah concat() boleh digunakan untuk menggabungkan berbilang tatasusunan.

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]

Kerumitan Masa: O(n) - Masa linear, dengan n ialah jumlah bilangan elemen dalam semua tatasusunan

Contoh 8: Menggunakan push() dengan Spread Operator

Anda boleh menggunakan push() dengan operator hamparan untuk memasukkan berbilang elemen pada penghujungnya.

let numbers = [1, 2, 3];
let newNumbers = [4, 5, 6];
numbers.push(...newNumbers);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]

Kerumitan Masa: O(m) - Masa linear, dengan m ialah bilangan elemen yang dimasukkan

Contoh 9: Memasukkan Tatasusunan ke Tatasusunan Lain

Begini cara anda boleh memasukkan keseluruhan tatasusunan ke dalam tatasusunan lain pada kedudukan tertentu.

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]

Kerumitan Masa: O(n) - Masa linear, dengan n ialah jumlah bilangan elemen dalam tatasusunan yang terhasil

5. Teknik Sisipan yang Cekap

Contoh 10: Praperuntukan Saiz Tatasusunan

Apabila anda mengetahui saiz akhir tatasusunan, praperuntukan boleh meningkatkan prestasi.

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]

Kerumitan Masa: O(n) - Masa linear, tetapi lebih cekap daripada mengembangkan tatasusunan secara dinamik

Contoh 11: Menggunakan Tatasusunan Ditaip untuk Data Berangka

Untuk tatasusunan besar data berangka, menggunakan tatasusunan ditaip boleh menjadi lebih cekap.

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]

Kerumitan Masa: O(n) - Masa linear, tetapi dengan kecekapan memori yang lebih baik untuk data berangka

Contoh 12: Sisipan Kelompok

Apabila memasukkan berbilang elemen, melakukannya secara berkelompok boleh menjadi lebih cekap daripada satu demi satu.

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

Kerumitan Masa: O(n) - Masa linear, tetapi dengan prestasi yang lebih baik untuk sisipan besar

6. Senario Sisipan Lanjutan

Contoh 13: Memasukkan ke dalam Tatasusunan Diisih

Apabila memasukkan ke dalam tatasusunan yang diisih, kita boleh menggunakan carian binari untuk mencari kedudukan yang betul.

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]

Kerumitan Masa: O(log n) untuk mencari kedudukan + O(n) untuk sisipan = O(n)

Contoh 14: Sisipan Penampan Pekeliling

Penimbal bulat ialah tatasusunan bersaiz tetap yang melilit. Berikut ialah pelaksanaan sisipan dalam penimbal bulat.

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:

1. Insert Interval
2. Merge Sorted Array
3. Insert Delete GetRandom O(1)
4. Search Insert Position
5. Array Partition I
6. Maximum Subarray
7. Move Zeroes
8. Sort Colors
9. Merge Intervals
10. Next Permutation
11. Find First and Last Position of Element in Sorted Array
12. 3Sum
13. Container With Most Water
14. Rotate Array
15. 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!

Atas ialah kandungan terperinci Sisipan Tatasusunan dalam DSA menggunakan JavaScript: Daripada Asas kepada Lanjutan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!