Insertion de tableaux dans DSA à l'aide de JavaScript : des bases à l'avancée

Les tableaux sont des structures de données fondamentales en informatique, et comprendre comment les manipuler efficacement est crucial pour tout développeur. Dans cet article de blog, nous approfondirons les techniques d'insertion de tableaux à l'aide de JavaScript, couvrant les concepts des niveaux de base aux niveaux avancés. Nous explorerons divers scénarios, fournirons 20 exemples, discuterons des complexités temporelles et aborderons même certains problèmes de style LeetCode.

Table des matières

1. Introduction aux tableaux
2. Insertion de base d'un tableau
3. Insertion à des positions spécifiques
4. Insérer plusieurs éléments
5. Techniques d'insertion efficaces
6. Scénarios d'insertion avancés
7. Problèmes de style LeetCode
8. Problèmes de pratique

1. Introduction aux tableaux

Un tableau est une collection d'éléments stockés dans des emplacements mémoire contigus. En JavaScript, les tableaux sont dynamiques, ce qui signifie qu’ils peuvent augmenter ou diminuer en taille. Avant de plonger dans les techniques d'insertion, récapitulons rapidement les bases des tableaux 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. Insertion de tableau de base

Exemple 1 : insertion à la fin (push)

Le moyen le plus simple d'insérer un élément dans un tableau est de l'ajouter à la fin en utilisant la méthode push().

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

Complexité temporelle : O(1) - Temps constant

Exemple 2 : insertion au début (unshift)

Pour insérer un élément au début d'un tableau, utilisez la méthode unshift().

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

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre d'éléments dans le tableau

Exemple 3 : Insertion à l'aide de l'opérateur Spread

L'opérateur spread peut être utilisé pour créer un nouveau tableau avec des éléments supplémentaires.

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

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre total d'éléments dans le nouveau tableau

3. Insertion à des positions spécifiques

Exemple 4 : Utilisation de splice() pour insérer à un index spécifique

La méthode splice() peut être utilisée pour insérer des éléments à une position spécifique dans le tableau.

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

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre d'éléments après le point d'insertion

Exemple 5 : insertion de plusieurs éléments avec splice()

Vous pouvez insérer plusieurs éléments à la fois en utilisant splice().

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

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre d'éléments après le point d'insertion

Exemple 6 : écrasement d'éléments

Vous pouvez également utiliser l'indexation de tableau pour écraser des éléments à des positions spécifiques.

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

Complexité temporelle : O(1) - Temps constant

4. Insertion de plusieurs éléments

Exemple 7 : concaténation de tableaux

La méthode concat() peut être utilisée pour combiner plusieurs tableaux.

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]

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre total d'éléments dans tous les tableaux

Exemple 8 : Utilisation de push() avec l'opérateur Spread

Vous pouvez utiliser push() avec l'opérateur spread pour insérer plusieurs éléments à la fin.

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

Complexité temporelle : O(m) - Temps linéaire, où m est le nombre d'éléments insérés

Exemple 9 : insertion d'un tableau dans un autre tableau

Voici comment insérer un tableau entier dans un autre à une position spécifique.

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]

Complexité temporelle : O(n) - Temps linéaire, où n est le nombre total d'éléments dans le tableau résultant

5. Techniques d'insertion efficaces

Exemple 10 : Préallocation de la taille du tableau

Lorsque vous connaissez la taille finale de la baie, la préallocation peut améliorer les performances.

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]

Complexité temporelle : O(n) - Temps linéaire, mais plus efficace que la croissance dynamique du tableau

Exemple 11 : Utilisation de tableaux typés pour les données numériques

Pour les grands tableaux de données numériques, l'utilisation de tableaux typés peut être plus efficace.

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]

Complexité temporelle : O(n) - Temps linéaire, mais avec une meilleure efficacité de mémoire pour les données numériques

Exemple 12 : Insertion par lots

Lors de l'insertion de plusieurs éléments, le faire par lots peut être plus efficace qu'un à la fois.

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

Complexité temporelle : O(n) - Temps linéaire, mais avec de meilleures performances pour les grandes insertions

6. Scénarios d'insertion avancés

Exemple 13 : insertion dans un tableau trié

Lors de l'insertion dans un tableau trié, nous pouvons utiliser la recherche binaire pour trouver la position correcte.

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]

Complexité temporelle : O(log n) pour trouver la position + O(n) pour l'insertion = O(n)

Exemple 14 : insertion de tampon circulaire

Un tampon circulaire est un tableau de taille fixe qui s'enroule. Voici une implémentation d'insertion dans un tampon circulaire.

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!

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!