摘要：說(shuō)明你可以假設(shè)數(shù)組中所有元素都是非負(fù)整數(shù)，且數(shù)值在位有符號(hào)整數(shù)范圍內(nèi)。提示按奇偶排序數(shù)組給定一個(gè)非負(fù)整數(shù)數(shù)組，中一半整數(shù)是奇數(shù)，一半整數(shù)是偶數(shù)。對(duì)數(shù)組進(jìn)行排序，以便當(dāng)為奇數(shù)時(shí)，也是奇數(shù)當(dāng)為偶數(shù)時(shí)，也是偶數(shù)。

原博客地址：https://finget.github.io/2019...

時(shí)間復(fù)雜度（運(yùn)行次數(shù)）

我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。

int aFunc(void) {
    printf("Hello, World!
");      //  需要執(zhí)行 1 次
    return 0;       // 需要執(zhí)行 1 次
}

那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算

int aFunc(int n) {
    for(int i = 0; i
這個(gè)方法需要 (n + 1 + n  + 1) = 2n + 2 次運(yùn)算。
我們把 算法需要執(zhí)行的運(yùn)算次數(shù) 用 輸入大小n 的函數(shù) 表示，即 T(n) 。
常用算法時(shí)間復(fù)雜度：

O(1)常數(shù)型
O(n)線性型
O(n^2)平方型
O(n^3)立方型
O(2^n)指數(shù)型
O(log2^n)對(duì)數(shù)型
O(nlog2^n)二維型

時(shí)間復(fù)雜度的分析方法： 
1、時(shí)間復(fù)雜度就是函數(shù)中基本操作所執(zhí)行的次數(shù) 
2、一般默認(rèn)的是最壞時(shí)間復(fù)雜度，即分析最壞情況下所能執(zhí)行的次數(shù) 
3、忽略掉常數(shù)項(xiàng) 
4、關(guān)注運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)，關(guān)注函數(shù)式中增長(zhǎng)最快的表達(dá)式，忽略系數(shù) 
5、計(jì)算時(shí)間復(fù)雜度是估算隨著n的增長(zhǎng)函數(shù)執(zhí)行次數(shù)的增長(zhǎng)趨勢(shì) 
6、遞歸算法的時(shí)間復(fù)雜度為：遞歸總次數(shù) * 每次遞歸中基本操作所執(zhí)行的次數(shù)
空間復(fù)雜度（占用內(nèi)存）
算法消耗的空間
一個(gè)算法的占用空間是指算法實(shí)際占用的輔助空間總和
算法的空間復(fù)雜度 
算法的空間復(fù)雜度不計(jì)算實(shí)際占用的空間，而是算整個(gè)算法的“輔助空間單元的個(gè)數(shù)”。算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)空間的數(shù)量級(jí)，它是問(wèn)題規(guī)模n的函數(shù)。記作：
S(n)=O(f(n)) 1
若算法執(zhí)行時(shí)所需要的輔助空間相對(duì)于輸入數(shù)據(jù)量n而言是一個(gè)常數(shù)，則稱這個(gè)算法的輔助空間為O(1); 
 遞歸算法的空間復(fù)雜度：遞歸深度N*每次遞歸所要的輔助空間， 如果每次遞歸所需的輔助空間是常數(shù)，則遞歸的空間復(fù)雜度是 O(N).
冒泡排序
原理：從第一個(gè)元素開(kāi)始，往后比較，遇到自己小的元素就交換位置
let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]

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

for (let j = 0; j < arr.length - 1 - i; j++)對(duì)于這里的理解：

當(dāng) i = 0 時(shí), j的最大值是arr.length-2,那最后一個(gè)值就不比嗎？并不是，if (arr[j] > arr[j + 1])如果j,j+1就會(huì)溢出。

那為什么又要-i呢，當(dāng)i=0時(shí),經(jīng)過(guò)第一次循環(huán)，最大值就會(huì)放到數(shù)組的最后一位，此時(shí)，在進(jìn)行第二次循環(huán)的時(shí)候i=1，最后的最大數(shù)就沒(méi)必要再比了，要比的就是前length-1-1項(xiàng),以此類推，可以減少循環(huán)次數(shù)，控制時(shí)間復(fù)雜度，所以j < arr.length - 1 - i。

// 另一種寫(xiě)法
let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]

function bubbleSort(arr) {
// 用i來(lái)做邊界最大值
  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;
}
bubbleSort(arr)
選擇排序
它的工作原理如下。首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。
let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]
function selectionSort(arr) {
  let len = arr.length;
  let min = ""; // 定一個(gè)最小值
  // i < len-1 * 因?yàn)閖 = i + 1,不然會(huì)重復(fù)比較一次最后一位
  for (let i = 0 ; i < len-1 ; i++) {
      min = i
    for (let j = i+1; j < len; j++) {
      if (arr[min] > arr[j]) {
        min = j
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]]
    console.log(`i=${i}; min=${min}; arr=${arr}`)
  }
  return arr;
}
selectionSort(arr)
// 循環(huán)過(guò)程
i=0; min=4; arr=3,19,90,9,89,21,5,77,10,22
i=1; min=6; arr=3,5,90,9,89,21,19,77,10,22
i=2; min=3; arr=3,5,9,90,89,21,19,77,10,22
i=3; min=8; arr=3,5,9,10,89,21,19,77,90,22
i=4; min=6; arr=3,5,9,10,19,21,89,77,90,22
i=5; min=5; arr=3,5,9,10,19,21,89,77,90,22
i=6; min=9; arr=3,5,9,10,19,21,22,77,90,89
i=7; min=7; arr=3,5,9,10,19,21,22,77,90,89
i=8; min=9; arr=3,5,9,10,19,21,22,77,89,90

最大間距
給定一個(gè)無(wú)序的數(shù)組，找出數(shù)組在排序之后，相鄰元素之間最大的差值。

如果數(shù)組元素個(gè)數(shù)小于 2，則返回 0。

示例?1:

輸入: [3,6,9,1]
輸出: 3
解釋: 排序后的數(shù)組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大差值 3。
示例?2:

輸入: [10]
輸出: 0
解釋: 數(shù)組元素個(gè)數(shù)小于 2，因此返回 0。
說(shuō)明:

你可以假設(shè)數(shù)組中所有元素都是非負(fù)整數(shù)，且數(shù)值在 32 位有符號(hào)整數(shù)范圍內(nèi)。
請(qǐng)嘗試在線性時(shí)間復(fù)雜度和空間復(fù)雜度的條件下解決此問(wèn)題。
var maximumGap = function(nums) {
    //if (nums.length < 2) {
        //return 0;
  //  }
    //nums.sort((a,b) =>  a-b)
    //let max = 0;
    //for(let i = 0; i< nums.length-1; i++) {
        //max = nums[i+1]-nums[i]>max?nums[i+1]-nums[i]:max
    //}
    //return max;
    if (nums.length < 2) {
        return 0;
    }
    nums.sort((a,b) =>  a-b)
    let max = 0,grap;
    for(let i = 0; i< nums.length-1; i++) {
        grap = nums[i+1]-nums[i]
        max = grap>max?grap:max
    }
    return max;
};
// leetcode上的優(yōu)解
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
  if (nums.length < 2) return 0
  let max = nums[0], min = nums[0]
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(nums[i], max)
    min = Math.min(nums[i], min)
  }
  let delta = (max - min) / (nums.length - 1)
  let maxBucket = new Array(nums.length - 1).fill(Number.MIN_SAFE_INTEGER)
  let minBucket = new Array(nums.length - 1).fill(Number.MAX_SAFE_INTEGER)
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] == min || nums[i] == max) continue
    let index = Math.floor((nums[i] - min) / delta)
    maxBucket[index] = Math.max(maxBucket[index], nums[i])
    minBucket[index] = Math.min(minBucket[index], nums[i])
  }
  let prev = min, maxGap = 0
  for (let i = 0; i < minBucket.length; i++) {
    if (minBucket[i] == Number.MAX_SAFE_INTEGER) continue
    maxGap = Math.max(minBucket[i] - prev, maxGap)
    prev = maxBucket[i]
  }
  maxGap = Math.max(max - prev, maxGap)
  return maxGap
};

// 輸入 [3,6,9,1]
// 最大值 9，最小值 1
// 最大桶 [-∞,-∞,-∞] 注意是反的，長(zhǎng)度比原數(shù)組少1
// 最小桶 [+∞,+∞,+∞] 注意是反的，長(zhǎng)度比原數(shù)組少1
// 平均桶間距 (9-1)/4 = 2
// 把值逐個(gè)放到桶 (nums[i]-最小值)/平均間距
// (3 - 1)/2 = 1 ，修改最小桶坐標(biāo)1為3， [+∞,3,+∞]，同理最大桶 [-∞,3,-∞]
// (6 - 1)/2 = 2.5 = 2， 最小桶 [+∞,3,6] 最大桶 [-∞,3,6]
// 9 為最大值，跳過(guò)
// 1 為最小值，跳過(guò)
// 如果有落在同一個(gè)桶的則最大桶取最大值，最小桶取最小值，此例子中沒(méi)有重復(fù)落入情況
// 從最小桶找到間隔最大的坐標(biāo) 最小值=1，最小桶 [+∞,3,6]，最大桶[-∞,3,6] 最大值=9
// 即較大間隔有3段，1-3(最小桶)，3(最大桶)-6(最小桶)，6(最大桶)-9
// 間隔 2,3,3 取最大 3
按奇偶排序數(shù)組
給定一個(gè)非負(fù)整數(shù)數(shù)組 A，返回一個(gè)數(shù)組，在該數(shù)組中，?A 的所有偶數(shù)元素之后跟著所有奇數(shù)元素。

你可以返回滿足此條件的任何數(shù)組作為答案。

?

示例：

輸入：[3,1,2,4]
輸出：[2,4,3,1]
輸出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也會(huì)被接受。
?

提示：

1 <= A.length <= 5000
0 <= A[i] <= 5000
var sortArrayByParity = function(A) {
    let arr = []
    for(let i = 0;i
按奇偶排序數(shù)組II
給定一個(gè)非負(fù)整數(shù)數(shù)組?A， A 中一半整數(shù)是奇數(shù)，一半整數(shù)是偶數(shù)。

對(duì)數(shù)組進(jìn)行排序，以便當(dāng)?A[i] 為奇數(shù)時(shí)，i?也是奇數(shù)；當(dāng)?A[i]?為偶數(shù)時(shí)， i 也是偶數(shù)。

你可以返回任何滿足上述條件的數(shù)組作為答案。

示例：

輸入：[4,2,5,7]
輸出：[4,5,2,7]
解釋：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也會(huì)被接受。
?

提示：

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
思路：利用雙指針，每次+2
var sortArrayByParityII = function(A) {
    let i = 0;
    let j = 1;
    while (j < A.length && i < A.length) {
        if (A[i] % 2 == 0) {
            i += 2;
        } else {
            while (A[j] % 2 != 0 && j < A.length) {
                j += 2;
            }
            if (j < A.length) {
                let tmp = A[i]
                A[i] = A[j]
                A[j] = tmp
            }
        }
    }
    return A;
};
缺失的第一個(gè)正數(shù)
給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。

示例?1:

輸入: [1,2,0]
輸出: 3
示例?2:

輸入: [3,4,-1,1]
輸出: 2
示例?3:

輸入: [7,8,9,11,12]
輸出: 1
說(shuō)明:

你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)，并且只能使用常數(shù)級(jí)別的空間。
// 第一種解法
function firstMissingPositive(arr) {
    // 過(guò)濾到非正數(shù)
    arr = arr.filter(item => item > 0);

    if(arr.length ==0) {
        // 數(shù)組為空說(shuō)明沒(méi)有正數(shù)，那最小的正數(shù)就是1
        return 1;
    } else {
        // 排序
        arr.sort((a,b) => a-b);
        // 如果第一項(xiàng)不是1，那就返回1
        if(arr[0] !== 1) {
            return 1
        } else {
            for (let i = 0,len = arr.length; i < len; i++) {
                if(arr[i+1] - arr[i] > 1) {
                    return arr[i] + 1
                } 
            }
            // 如果上面沒(méi)有return，那就返回?cái)?shù)組最后一項(xiàng) + 1
            return arr.pop() + 1
        }
    }
};
// 利用選擇排序優(yōu)化代碼性能,上面那種寫(xiě)法，最大的缺點(diǎn)就是對(duì)所有數(shù)據(jù)都進(jìn)行了排序
function firstMissingPositive(arr) {
    arr = arr.filter(item => item > 0);

    // 選擇排序，先拿到最小值，如果第一個(gè)元素不是1就返回1
    let min = 0;
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        min = i;
        for (let j = i+1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        [arr[i], arr[min]] = [arr[min], arr[i]]
        // 當(dāng)進(jìn)行到第二次遍歷后，就可以比較了
        if (i>0) {
            if(arr[i]-arr[i-1]>1) {
                return arr[i-1] + 1
            }
        } else {
            // 如果第一項(xiàng)最小正數(shù)不是1，就返回1 
            if (arr[0]!==1){
                return 1;
            }
        }
    }
    // 上面的情況都沒(méi)通過(guò)，這也是最壞的情況，就判斷數(shù)組的長(zhǎng)度如果為0就返回1，反之返回?cái)?shù)組最后一項(xiàng)+1
    return arr.length?arr.pop() + 1:1
}
最后
創(chuàng)建了一個(gè)前端學(xué)習(xí)交流群，感興趣的朋友，一起來(lái)嗨呀！