時間/空間復雜度

補充：空間復雜度，如果一個函數(shù)運行下來劣针，占用的內(nèi)存是3個字節(jié)，那么空間復雜度是O(1)亿扁。如果占用的內(nèi)存字節(jié)數(shù)跟邏輯處理是線性關(guān)系捺典，那么空間復雜度就是O(n)。
總結(jié)：時間復雜度从祝，看的是運行次數(shù)襟己，空間復雜度，看的是占用的內(nèi)存哄褒。

（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時間復雜度（算法的時間復雜度）

image.png

冒泡排序

思路：每一輪都兩兩比較稀蟋，把其中較大的數(shù)放到右邊

// 冒泡排序
function bubbleSort(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

選擇排序

思路：每一輪都會選擇中最小的一個數(shù)，把這個數(shù)放到左邊

// 選擇排序
function selectSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[i]) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
    }
    return arr;
}

題目： 922. 按奇偶排序數(shù)組 II

思路：首先設(shè)定目標數(shù)組奇數(shù)位和偶數(shù)位游標呐赡，然后遍歷源數(shù)組退客，如果是奇數(shù)就放到奇數(shù)位游標的位置上，如果是偶數(shù)就放到偶數(shù)位游標的位置上。

function sortArrayByParity(arr) {
    // 進行升序排序
    arr.sort((a, b) => a - b);
    // 聲明一個空數(shù)組用來存儲奇偶排序后的數(shù)組
    let r = [];
    // 記錄奇數(shù)萌狂，偶數(shù)位下標
    let odd = 1;
    let even = 0;
    // 對數(shù)組進行遍歷
    arr.forEach(item => {
        if (item % 2 === 1) {
            r[odd] = item;
            odd += 2;
        } else {
            r[even] = item;
            even += 2;
        }
    });
    return r;
}

題目： 215. 數(shù)組中的第K個最大元素

常規(guī)做法：先降序排序档玻，然后取第k個元素

function findKthLargest(arr, k) {
    return arr.sort((a, b) => b - a)[k - 1];
}

弊端：性能不好，其實沒有必要全部都排序好

更好做法：冒泡排序做到第k次

function findKthLargest(arr, k) {
    for (let i = arr.length - 1; i > arr.length - 1 - k; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr[arr.length - k];
}

說明：雖然代碼量比方法1要多茫藏，但是性能提高了

題目：164. 最大間距

常規(guī)做法：先降序排序误趴，然后取第k個元素

function maximumGap(arr) {
    // 如果長度小于2，返回0
    if (arr.length < 2) {
        return 0;
    }
    // 排序
    arr.sort();
    // 保存相鄰元素的最大差值
    let max = 0;
    let tmp = 0;
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        tmp = arr[i + 1] - arr[i];
        if (tmp > max) {
            max = tmp;
        }
    }
    return max;
}

弊端：同時有sort()和for循環(huán)务傲，性能不好

更好做法：在冒泡排序的每一輪中取得最大兩個元素間的差值

function maximumGap(arr) {
    // 如果長度小于2凉当，返回0
    if (arr.length < 2) {
        return 0;
    }
    // 保存相鄰元素的最大差值
    let max = 0;
    let tmp = 0;
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }   
        // 從第二輪開始計算差值
        if (i < arr.length - 1) {
            tmp = arr[i + 1] - arr[i];
        }
        if (tmp > max) {
            max = tmp;
        }
    }
    // 注意還需要跟arr[1] - arr[0]的結(jié)果做比較
    return Math.max(max, arr[1] - arr[0]);
}

說明：相比常規(guī)做法，少做了一次for循環(huán)售葡，性能更好

題目：41. 缺失的第一個正數(shù)

常規(guī)做法：先排序再找缺失的正數(shù)

function firstMissingPositive(arr) {
    // 過濾掉非正數(shù)
    arr = arr.filter(item => item > 0);
    // 正整數(shù)數(shù)組是不是空
    if (arr.length) {
        // 升序看杭，目的：方便從左到右取最小值arr[0]
        arr.sort();
        // 如果第一個元素不為1，返回1
        if (arr[0] !== 1) {
            return 1;
        } else {
            // 從左到右遍歷挟伙，只要下一個元素和當前元素的差值 >1楼雹，返回當前元素的下一個值(+1)
            for (let i = 0; i < arr.length - 1; i++) {
                if (arr[i + 1] - arr[i] > 1) {
                    return arr[i] + 1;
                }
            }
            // 如果數(shù)組是連續(xù)的正數(shù)[1,2,3,4,5,6]
            return arr.pop() + 1;
        }
    } else {
        return 1;
    }
}

弊端：同時有sort()和for循環(huán)，性能不好

更好做法：在選擇排序的每一輪中找缺失的正數(shù)

function firstMissingPositive(arr) {
    // 過濾掉非正數(shù)
    arr = arr.filter(item => item > 0);
    let len = arr.length;
    // 正整數(shù)數(shù)組是不是空
    if (len) {
        for (let i = 0; i < len; i++) {
            for (let j = i + 1; j < len; j++) {
                if (arr[j] < arr[i]) {
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                }
            }
            // arr[i]是本輪中最小的數(shù)
            if (i > 0) {
                // 當前元素與前一個元素的差值 >1尖阔，返回前一個元素的下一個值(+1)
                if (arr[i] - arr[i - 1] > 1) {
                    return arr[i - 1] + 1;
                }
            } else {
                // 如果第一個元素不為1贮缅，返回1
                if (arr[i] !== 1) {
                    return 1;
                }
            }
        }
        return arr.pop() + 1;
    } else {
        return 1;
    }
}

說明：相比常規(guī)做法，少做了一次for循環(huán)介却，性能更好

基礎(chǔ)算法之"排序類"