一 技巧基礎

二 136. 只出現一次的數字

1 題目

2 解題思路

哈希表map

其實看到題目數組中某個元素出現的次數也可以直接用unordered_map容器統計每一個元素出現的次數，然后在遍歷整個map容器查看是否有元素出現的次數等于1

3 code

class Solution {
public:int singleNumber(vector<int>& nums) {//第一次遍歷，使用哈希來統計數組中元素出現次數unordered_map<int,int> map;for(int num:nums){map[num]++;}//第二次遍歷，查看是否有元素出現的次數等于1for(int num:nums){if(map[num]==1) return num;}return 0;}
};

三 169. 多數元素

1 題目

2 解題思路

本題常見的三種解法：

• 哈希表統計法： 遍歷數組 nums ，用 HashMap 統計各數字的數量，即可找出 眾數 。此方法時間和空間復雜度均為 O(N)O(N)O(N) 。
• 數組排序法： 將數組 nums 排序，數組中點的元素 一定為眾數。
• 摩爾投票法： 核心理念為 票數正負抵消 。此方法時間和空間復雜度分別為 O(N)O(N)O(N) 和 O(1)O(1)O(1) ，為本題的最佳解法。

哈希表+打擂臺（邊哈希，邊打擂臺，省去二次遍歷哈希表在麻煩）

我們使用哈希映射（HashMap）來存儲每個元素以及出現的次數。對于哈希映射中的每個鍵值對，鍵表示一個元素，值表示該元素出現的次數。

我們用一個循環遍歷數組 nums 并將數組中的每個元素加入哈希映射中。在這之后，我們遍歷哈希映射中的所有鍵值對，返回值最大的鍵。我們同樣也可以在遍歷數組 nums 時候使用打擂臺的方法，維護最大的值，這樣省去了最后對哈希映射的遍歷。

3 code

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int>map;//哈希int majority=0,cnt=0;//打擂臺//哈希for(int num:nums){map[num]++;//打擂臺if(map[num]>cnt){majority=num;cnt=map[num];}}return majority;}
};

四 75. 顏色分類

1 題目

2 解題思路

首先，所有數都≤2，那么索性把所有數組置為2，然后遇到所有≤1的，就再全部置為1，，覆蓋了錯誤的2，這時候所有2的位置已經正確，最后所有≤0的全部置為0，也就覆蓋了一些錯誤的1，這時候，0和1的位置都正確。最重要的就是需要兩個指針指向下一個1或0的位置

3 code

class Solution {
public:void sortColors(vector<int>& nums) {int n0=0,n1=0;for(int i=0;i<nums.size();i++){int num=nums[i];//先將所有在數置為2nums[i]=2;//如果數值小于等于1，將數置為1//(為0的時候，會將1的計數位前推一位)if(num<=1){nums[n1]=1;n1++;}//如果數值小于等于0，將數置為0if(num<=0){nums[n0]=0;n0++;}}}
};

五 31. 下一個排列

1 題目

2 解題思路

這道題是根據 維基百科 ,下圖所示:

翻譯過來：

先找出最大的索引 k 滿足 nums[k] < nums[k+1]，如果不存在，就翻轉整個數組；
再找出另一個最大索引 l 滿足 nums[l] > nums[k]；
交換 nums[l] 和 nums[k]；
最后翻轉 nums[k+1:]。
舉個例子：

比如 nums = [1,2,7,4,3,1]，下一個排列是什么？

我們找到第一個最大索引是 nums[1] = 2

再找到第二個最大索引是 nums[4] = 3

交換，nums = [1,3,7,4,2,1];

翻轉，nums = [1,3,1,2,4,7]

完畢!

所以,

時間復雜度：O(n)O(n)O(n)

空間復雜度：O(1)O(1)O(1)

3 code

class Solution {
public:void nextPermutation(vector<int>& nums) {int cur=nums.size()-2;//前面大于后面在while(cur>=0&&nums[cur]>=nums[cur+1]){cur--;}//已經是最大數組了if(cur<0){sort(nums.begin(),nums.end());}else{//表示找到國降序在一個位置int pos=nums.size()-1;while(nums[pos]<=nums[cur]){pos--;}swap(nums[cur],nums[pos]);reverse(nums.begin()+cur+1,nums.end());}}
};

六 31. 下一個排列

1 題目、

2 解題思路

題目要求查找重復的整數，很容易想到使用「哈希表」，但是題目中要求「只用常量級 O(1 的額外空間」，該方法不符合題意；
還可以考慮使用「力扣」第 41 題：缺失的第一個正數 的技巧，使用「原地哈希」，但是題目要求「你設計的解決方案必須不修改數組 nums」，該方法不符合題意；
但是題目中還說：「數字都在 1 到 n 之間（包括 1 和 n）」，查找一個有范圍的整數，可以使用「二分查找」（這一點很重要，很多「二分查找」的問題就是要我們找一個整數）；
「快慢指針」的做法很有技巧，具體做法請見其它題解。

可以使用「二分查找」的原因

因為題目要找的是一個 整數，并且這個整數有明確的范圍，所以可以使用「二分查找」。

重點理解：

這個問題使用「二分查找」是在數組 [1, 2,…, n] 中查找一個整數，而 并非在輸入數組數組中查找一個整數。

使用「二分查找」查找一個整數，這是「二分查找」的典型應用，經常被稱為「二分答案」。在 題解 中，「題型二」與「題型三」都是這樣的問題。

央視《幸運 52》節目的「猜價格游戲」，就是「二分答案」。玩家猜一個數字，如果猜中，游戲結束，如果主持人說「猜高了」，應該猜一個更低的價格，如果主持人說「猜低了」，應該猜一個更高的價格。

繼續 解題思路：每一次猜一個數，然后 遍歷整個輸入數組，進而縮小搜索區間，最后確定重復的是哪個數。

理解題意：

n + 1 個整數，放在長度為 n 的數組里，根據「抽屜原理」，至少會有 1 個整數是重復的；
抽屜原理：把 10 個蘋果放進 9 個抽屜，至少有一個抽屜里至少放 2 個蘋果。

方法：二分查找

「二分查找」的思路是先猜一個數（搜索范圍 [left…right] 里位于中間的數 mid），然后統計原始數組中 小于等于 mid 的元素的個數 count：

如果 count 嚴格大于 mid。根據 抽屜原理，重復元素就在區間 [left…mid] 里；
否則，重復元素可以在區間 [mid + 1…right] 里找到，其實只要第 1 點是對的，這里肯定是對的，但要說明這一點，需要一些推導，我們放在最后說。

方法：快慢指針

數組形式的鏈表

題目設定的問題是 N+1 個元素都在 [1,n] 這個范圍內。這樣我們可以用那個類似于 ‘缺失的第一個正數’ 這種解法來做，但是題意限制了我們不能修改原數組，我們只能另尋他法。也就是本編題解講的方法，將這個題目給的特殊的數組當作一個鏈表來看，數組的下標就是指向元素的指針，把數組的元素也看作指針。如 0 是指針，指向 nums[0]，而 nums[0] 也是指針，指向 nums[nums[0]].
這樣我們就可以有這樣的操作

C++
int point = 0;
while(true){point = nums[point]; // 等同于 next = next->next; 
}

鏈表中的環

假設有這樣一個樣例：[1,2,3,4,5,6,7,8,9,5]。如果我們按照上面的循環下去就會得到這樣一個路徑：1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9] . . .這樣就有了一個環，也就是 6 7 8 9。point 會一直在環中循環的前進。
這時我們設置兩個一快(fast)一慢(slow)兩個指針，一個每次走兩步，一個每次走一步，這樣讓他們一直走下去，直到他們在重復的序列中相遇，

3 code

二分查找

class Solution {
public:int findDuplicate(vector<int>& nums) {int len=nums.size();int left=1;int right=len-1;while(left<right){int mid=(left+right)/2;//nums中小于等于mid的元素的個數int count=0;for(int num:nums){if(num<=mid){count++;}}if(count>mid){//下一輪搜索的區間[left..mid]right=mid;}else{//下一輪搜索的區間[mid+1..right]left=mid+1;}}//退出循環以后 left 與 right 重合，left （或者 right）就是我們要找的重復的整數；return left;}
};

快慢指針

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int slow = 0;int fast = 0;//快慢指針相遇while (true) {slow = nums[slow];fast = nums[nums[fast]];if (slow == fast) break;}//快指針返回終點，繼續出發fast = 0;while (nums[slow] != nums[fast]) {slow = nums[slow];fast = nums[fast];}return nums[slow];}
};