配列はコンピューターサイエンスにおける基本的なデータ構造であり、配列を効率的に操作する方法を理解することは開発者にとって非常に重要です。このブログ投稿では、JavaScript を使用した配列挿入テクニックを詳しく掘り下げ、基本レベルから高度なレベルまでの概念をカバーします。さまざまなシナリオを検討し、20 の例を示し、時間の複雑さについて説明し、さらに LeetCode スタイルの問題にも取り組みます。
目次
- 配列の概要
- 基本的な配列の挿入
- 特定の位置への挿入
- 複数の要素の挿入
- 効率的な挿入テクニック
- 高度な挿入シナリオ
- LeetCode スタイルの問題
- 練習問題
1. 配列の概要
配列は、連続したメモリ位置に格納される要素のコレクションです。 JavaScript では、配列は動的です。つまり、サイズが拡大または縮小する可能性があります。挿入テクニックに入る前に、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. 基本的な配列の挿入
例1：最後に挿入（プッシュ）
配列に要素を挿入する最も簡単な方法は、push() メソッドを使用して要素を最後に追加することです。
let numbers = [1, 2, 3];
numbers.push(4);
console.log(numbers); // Output: [1, 2, 3, 4]
ログイン後にコピー
時間計算量: O(1) - 定数時間
例 2: 先頭に挿入する (シフト解除)
配列の先頭に要素を挿入するには、unshift() メソッドを使用します。
let colors = ['red', 'green'];
colors.unshift('blue');
console.log(colors); // Output: ['blue', 'red', 'green']
ログイン後にコピー
時間計算量: O(n) - 線形時間、n は配列内の要素の数です
例 3: スプレッド演算子を使用した挿入
スプレッド演算子を使用して、追加の要素を含む新しい配列を作成できます。
let animals = ['cat', 'dog'];
let newAnimals = ['bird', ...animals, 'fish'];
console.log(newAnimals); // Output: ['bird', 'cat', 'dog', 'fish']
ログイン後にコピー
時間計算量: O(n) - 線形時間、n は新しい配列内の要素の総数です
3. 特定の位置に挿入する
例 4: splice() を使用して特定のインデックスに挿入する
splice() メソッドを使用して、配列内の特定の位置に要素を挿入できます。
let fruits = ['apple', 'banana', 'orange'];
fruits.splice(1, 0, 'mango');
console.log(fruits); // Output: ['apple', 'mango', 'banana', 'orange']
ログイン後にコピー
時間計算量: O(n) - 線形時間、n は挿入ポイント以降の要素の数です
例 5: splice() を使用した複数の要素の挿入
splice() を使用すると、複数の要素を一度に挿入できます。
let numbers = [1, 2, 5, 6];
numbers.splice(2, 0, 3, 4);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]
ログイン後にコピー
時間計算量: O(n) - 線形時間、n は挿入ポイント以降の要素の数です
例 6: 要素の上書き
配列インデックスを使用して、特定の位置の要素を上書きすることもできます。
let letters = ['A', 'B', 'D', 'E'];
letters[2] = 'C';
console.log(letters); // Output: ['A', 'B', 'C', 'E']
ログイン後にコピー
時間計算量: O(1) - 定数時間
4. 複数の要素の挿入
例 7: 配列の連結
concat() メソッドを使用して、複数の配列を結合できます。
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]
ログイン後にコピー
時間計算量: O(n) - 線形時間、n はすべての配列の要素の合計数です
例 8: スプレッド演算子での Push() の使用
スプレッド演算子とともにpush()を使用すると、最後に複数の要素を挿入できます。
let numbers = [1, 2, 3];
let newNumbers = [4, 5, 6];
numbers.push(...newNumbers);
console.log(numbers); // Output: [1, 2, 3, 4, 5, 6]
ログイン後にコピー
時間計算量: O(m) - 線形時間、m は挿入される要素の数です
例 9: 配列を別の配列に挿入する
配列全体を別の配列の特定の位置に挿入する方法は次のとおりです。
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]
ログイン後にコピー
時間計算量: O(n) - 線形時間、n は結果の配列内の要素の総数です
5. 効率的な挿入技術
例 10: 配列サイズの事前割り当て
配列の最終的なサイズがわかっている場合、事前割り当てによりパフォーマンスが向上する可能性があります。
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]
ログイン後にコピー
時間計算量: O(n) - 線形時間ですが、配列を動的に拡張するよりも効率的です
例 11: 数値データに型付き配列を使用する
数値データの大きな配列の場合は、型付き配列を使用する方が効率的です。
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]
ログイン後にコピー
時間計算量: O(n) - 線形時間ですが、数値データのメモリ効率が向上します
例 12: バッチ挿入
複数の要素を挿入する場合、一度に 1 つずつ挿入するよりもバッチで実行した方が効率的です。
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
ログイン後にコピー
時間計算量: O(n) - 線形時間ですが、大規模な挿入のパフォーマンスが向上します
6. 高度な挿入シナリオ
例 13: ソートされた配列への挿入
ソートされた配列に挿入する場合、二分検索を使用して正しい位置を見つけることができます。
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]
ログイン後にコピー
時間計算量: 位置検索の O(log n) + 挿入の O(n) = O(n)
例 14: 循環バッファの挿入
循環バッファーは、循環する固定サイズの配列です。これは循環バッファへの挿入の実装です。
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:
- Insert Interval
- Merge Sorted Array
- Insert Delete GetRandom O(1)
- Search Insert Position
- Array Partition I
- Maximum Subarray
- Move Zeroes
- Sort Colors
- Merge Intervals
- Next Permutation
- Find First and Last Position of Element in Sorted Array
- 3Sum
- Container With Most Water
- Rotate Array
- 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!
以上がJavaScript を使用した DSA への配列挿入: 基本から高度までの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
