目錄

初遇🌖（資料結構是什么？）

演算法·出現🌗

演算法·效率🌘

時間復雜度🌕

·時間復雜度的身世🙋?♂?

·大O的漸進表示法🤳

推導大O階方法：

時間復雜度身世之別🌟

案例1

案例2

案例3 .strchr

案例4.冒泡排序

案例5.二分查找

案例6.階乘遞回

案例7.斐波那契遞回

空間復雜度🌔

她的身世🧏🏻?♀?

案例1.冒泡排序?

案例2.斐波那契陣列

案例3.階乘遞回

1??·leetcode 面試題17.04 消失的數字

思路1-排序

思路2-數列和

思路3-異或^

2??·leetcode 劍指offer56-I. 陣列中數字出現的次數

思路1.

初遇🌖（資料結構是什么？）

我：嗨，你好！資料結構，你是誰？

她：我是計算機存盤、組織資料的方式；具體來說就是指相互之間存在一種或多種特定關系的資料元素的集合！

我：閣下當真是計算機江湖中的最強女俠！

她：不敢當，小兄弟，我還有一個閨蜜和我共闖江湖！

我：敢問她是？

演算法·出現🌗

她：她是演算法（Algorith），就是定義良好的計算程序，她取一個或一組的值為輸入，并產生出一個或一組值作為輸出，簡單來說，演算法就是一系列的計算步驟，用來將輸入資料轉化為輸出的結果，

演算法·效率🌘

江湖中，傳聞，演算法效率有時空之分，具體來說便是時間效率與空間效率之分

時間效率被稱為時間復雜度——衡量一個演算法的運行速度

空間效率被稱為空間復雜度——衡量一個演算法所需的額外空間

在計算機發展早期，計算機存盤容量很小，所以很在意空間復雜度；但是時光流逝，如今計算機的江湖之中，存盤容量已到達極之巔峰，我們已無需特別關注演算法復雜度了

時間復雜度🌕

---

·時間復雜度的身世🙋?♂?

演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，

一個演算法所花費的時間與其中陳述句的執行次數成正比，演算法中的基本操作的執行次數，為演算法的時間復雜度

---

·大O的漸進表示法🤳

實際中我們計算時間復雜度只需要計算大概執行次數，那么我們使用大O的漸進表示法，

大O符號：用于描述函式漸進式行為的數學符號

---

推導大O階方法：

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，

---

時間復雜度身世之別🌟

最壞情況：任意輸入規模的最大運行次數（上界）
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數（下界）

案例1

---

案例2

---

案例3 .strchr

---

案例4.冒泡排序

---

案例5.二分查找

時間復雜度中，習慣將log2(N) 簡寫為 logN

---

案例6.階乘遞回

---

案例7.斐波那契遞回

???????

空間復雜度🌔

---

她的身世🧏🏻?♀?

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少 bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，

---

案例1.冒泡排序

---

案例2.斐波那契陣列

---

案例3.階乘遞回

1??·leetcode 面試題17.04 消失的數字

---

思路1-排序

采用冒泡排序—— 時間復雜度：O(N^2)

采用快排qsort——時間復雜度：O(N*logN)

以上演算法時間復雜度均未滿足

---

思路2-數列和

（0-n計算等引數列的和）-（陣列中的值相加）

O(1) O(N)

演算法時間復雜度滿足√

具體實作：

int missingNumber(int* nums, int numsSize){
    int sum1=0 , sum2=0 ,ret=0;
    for(int i=0;i<numsSize;++i)
    {
        sum2+=nums[i];//計算數列中的和
    }//時間復雜度為O(N)
    sum1=numsSize*(numsSize+1)/2;//計算0-n的等引數列之和
    ret=sum1-sum2;
    return ret;
}

---

思路3-異或^

前情提要：對于一組數字，不論其中的異或順序，只要在對這組數字異或程序中有兩個相同，那么這兩個陣列異或的最終結果為0

對于本題，可先對0-n的連續數字異或一遍，接著對含有欠缺數字的陣列中的每個數字異或，那么該陣列中未欠缺的數字和0-n連續數字會異或2次，結果為0；而因為陣列中缺少1位數字，原先0-n的連續數字中必有1位只參與了異或1次，即為本身，得解，

具體實作：

int missingNumber(int* nums, int numsSize){
    int sum=0;
    for(int i=0;i<numsSize;++i)
    {
        sum^=nums[i];//計算數列中的異或
    }//時間復雜度為O(N)
    
    for(int j=0;j<numsSize+1;++j)
    {
        sum^=j;//求0-n的異或
    }//時間復雜度為O(N)

    return sum;
}

2??·leetcode 劍指offer56-I. 陣列中數字出現的次數

---

思路1.

1.前情提要：將陣列中的數挨個異或，會抵消兩個相同數字，只出現一次的數字會異或成一個數,這里假定這個數為a

2.現在的問題是，如何在這一個數a中區分出兩個單獨的數字：我們可以肯定的是這個數a必然不可能為全0；那么這數a的二進制形式中必有至少一個位置為1，而這個位置的1就是區分這兩個單獨數字的位置，這兩個單獨數字在a的1這一位上必然一個為0，一個為1

3.思路綜合：先將陣列中數字異或得a----->在a中找一個值為1的位---->在原陣列中通過這個位置進行分組---->在對應的各組內會出現重復數字和單獨出現一次的數字--->組內異或---> √

具體實作：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 //return 的陣列必須是被malloc的
int* singleNumbers(int* nums, int numsSize, int* returnSize){
    int x=0, y=0;
    int ret=0;
    for(int i=0;i<numsSize;++i)
    {
        ret^=nums[i];
    }
    //從低到高找第一個出現的1
    int j=0;
    for(;j<32;++j)
    {
        if((ret>>j)&1)
        break;
    }
    //ret 的第j位為1，說明X和y兩個的第j位一個位1一個位0
    //將原陣列分為兩組，第j位為1的為a組，第j為為0的為b組
    //a,b組資料變成其他數出現2次
    for(int i=0;i<numsSize;++i)
    {
        if((nums[i]>>j)&1)//a組
        {
            x^=nums[i];
        }
        else//b組
        {
            y^=nums[i];
        }
    }
    int*arr=(int*)malloc(sizeof(int)*2);
    arr[0]=x;
    arr[1]=y;
    *returnSize=2;
    return arr;
}