データストラクチャー Arrays

Data Structure Array

Static arrayとDynamic arrayがある。Jsなどのhigh level languageでは特に意識することないが、low level languageなどでは気にする必要がある。 JavaでいうArrayはstatic / ArrayListはdynamicにあたる。

ArraysのBigO

Static	Dynamic	Big O
lookup	lookup	O(1)
push	append	O(1)
insert	insert	O(n)
delete	delete	O(n)

※appendはO(n)になり得る。

Ex)

const string = ['a', 'b', 'c', 'd', 'e'];
// 4 * 4 の16bytesのstorage

strings.push('e');  // O(1)
strings.push();  // O(1)
strings.unshift('x');  // O(n)
strings.splice(2, 0, 'e');  // O(n)

unshiftとspliceがO(n)になる理由は、値が配列の先頭または指定箇所に代入されることによって、 それまでのindexの位置がループによって書き換えられるため。

class MyArray{
    constructor() {
        this.length = 0;
        this.data = {};
    }

    get(index) {
        return this.data[index];
    }

    push(item) {
        this.data[this.length] = item;
        this.length++;
        return this.length;
    }

    pop(){
        const lastItem = this.data[this.length -1];
        delete this.data[this.length-1];
        this.length--;
        return lastItem;
    }

    delete(index) {
        const item = this.data[index];
        this.shuftItems(index);
        return item;
    }

    shuftItems(index) {
        for(let i = index; i < this.length -1; i++){
            this.data[i] = this.data[i+1];
        }
        delete this.data[this.length-1];
        this.length--;
    }
}

const newArray = new MyArray();
newArray.push('hi');
newArray.push('world');
newArray.pop();
console.log(newArray);

Ex1) Reverse String

const reverseString = (string) => {
    let arr = string.split("");
    let reverseArr = [];
    for(let i = 0; i < arr.length; i++){
        reverseArr.unshift(arr[i]);
    }

    console.log(reverseArr.join(''))
}

reverseString("apple is good");

const reverseString2 = (string) => {
    // check input
    if(!string || string.length < 2 || typeof string !== 'string') {
        return "that is not good";
    }

    const backwords = [];
    const totalItems = string.length - 1;
    for(let i = totalItems; i >= 0; i--){
        backwords.push(string[i]);
    }
    return backwords.join('');
}

const reverseString3 = (str) => {
    return str.split('').reverse().join();
}

const reverseString4 = (str) => str.split('').reverse().join();

const reverseString5 = str => [...str].reverse().join();

console.log(reverseString2("banana is soso"));

Data Structureの問題を解く際に、inputのチェックをすることが大事。

EX2) MergeSortedArray

mergeSortedArrays([0,3,4,31], [4,6,30]);


const mergeSortedArrays = (arr1, arr2) => {
    const arr = arr1.concat(arr2);
    arr.sort((a, b) => a-b);
    console.log(arr.join(','));
}


const mergeSortedArrays1 = (arr1, arr2) => {
    const mergedArray = [];
    let array1Item = arr1[0];
    let array2Item = arr2[0];
    let i = 1;
    let j = 1;

    // check input
    if(arr1.length === 0) {
        return arr2;
    }
    if(arr2.length === 0){
        return arr1;
    }

    while(array1Item || array2Item) {
        if(!array2Item || array1Item < array2Item) {
            mergedArray.push(array1Item);
            array1Item = arr1[i];
            i++;
        } else {
            mergedArray.push(array2Item);
            array2Item = arr2[j];
            j++;
        }
    }
    return mergedArray;
}

console.log(mergeSortedArrays1([0,3,4,31], [4,6,30]));

ArraysのProsとCons

Pros	Cons
Fast lookups	Slow Inserts
Fast push/pop	Slow deletes
Ordered	Fixed size*

*static Arrayを使う場合