如有缺漏謬誤，還請批評指正。

1.只出現一次的數字

? ? ? ?利用異或運算相同得0的特點。所有出現過兩次的數字都會在異或運算累加過程中被抵消。

class Solution {
public:int singleNumber(vector<int>& nums) {int res=0;for(int i=0;i<nums.size();i++) res^=nums[i];return res;}
};

2.多數元素

? ? ? ? 隨機取數，然后判斷是否是答案。因為眾數被選中的概率大于50%，所以時間復雜度雖然理論上可能出現O(∞)的情況，但實際上可以達到O(n)。

class Solution {
public:int majorityElement(vector<int>& nums) {while(true){int candidate=nums[rand()%nums.size()];int count=0;for(int i=0;i<nums.size();i++){if(nums[i]==candidate){count++;if (count>nums.size()/2) return candidate;}}}return -1;}
};

3.顏色分類

????????經典的“荷蘭國旗”問題。

（1）單指針解法

class Solution {
public:void sortColors(vector<int>& nums) {int i=0;for(int j=0;j<nums.size();j++){if(nums[j]==0){swap(nums[i],nums[j]);i++;}}for(int j=i;j<nums.size();j++){if(nums[j]==1){swap(nums[i],nums[j]);i++;}}}
};

（2）雙指針解法

? ? ? ? 比單指針少了一趟遍歷。

①兩個同向指針分別記錄0的交換位置和1的交換位置。

class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int ptr0=0,ptr1=0;for(int i=0;i<n;i++){if(nums[i]==0){swap(nums[i],nums[ptr0++]);if(ptr1<ptr0) ptr1++;}if(nums[i]==1) swap(nums[i],nums[ptr1++]);}}
};

②左右指針分別記錄0的交換位置和2的交換位置。?

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int r0=0,l2=n-1;  // r0: 0的右邊界，l2:2的左邊界for(int i=0;i<=l2;i++){       // 必須包含等于，因為nums[r]可能還沒處理if(nums[i]==0) swap(nums[i],nums[r0++]);  // 0交換到左邊，r0右移//換完后的理想狀態：換過后nums[i]是1(1處在0的右邊界和2的左邊界之間)else if(nums[i]==2){swap(nums[i],nums[l2--]);  // 2交換到右邊，l2左移if(nums[i]!=1) i--;  //num[i]==0的情況：2和0換，換過后的0需再換一遍到左邊界//num[i]==2的情況：2和2換，換過后的2需重新處理}}}
};

4.下一個排列

三個關鍵步驟：

• 找到?i：i是第一個破壞從后向前升序的位置，這意味著nums[i]可以增大以得到更大的排列。

• 找到?j：nums[j]?是?i?之后比?nums[i]?大的最小數，交換后?nums[i]增大，但?i?之后的部分仍然降序。

• 反轉：反轉?i+1之后的部分使其升序，這樣這部分最小，確保了整個排列是“下一個”排列。

class Solution {
public:void nextPermutation(vector<int>& nums) {int n=nums.size();int i=n-2;// 1. 找到第一個不符合逆序升的nums[i]while(i>=0&&nums[i]>=nums[i+1]) i--;// 2. 再找第一個比nums[i]大的nums[j]，swap兩個數if(i>=0){int j=n-1;while(j>=0&&nums[j]<=nums[i]) j--;swap(nums[i], nums[j]);}// 3.反轉 i+1 到末尾的部分（使其升序）reverse(nums.begin()+i+1, nums.end());}
};

5.多數問題

核心思想：將數組視為鏈表，并利用快慢指針檢測環。

相遇的地點是環的入口（即重復數字）：推導如下。

class Solution {
public:int findDuplicate(vector<int>& nums) {// 初始化快慢指針，初始位置在數組的起始位置（索引0）int slow=0,fast=0;// 第一階段：檢測環的存在（Floyd's Tortoise and Hare算法）do{slow=nums[slow];       // 慢指針每次移動一步fast=nums[nums[fast]]; // 快指針每次移動兩步} while (slow!=fast);      // 當快慢指針相遇時，說明存在環// 第二階段：找到環的入口（即重復的數字）slow=0; // 將慢指針重置到起點while(slow!=fast){slow=nums[slow]; // 慢指針每次移動一步fast=nums[fast]; // 快指針每次移動一步}// 最終相遇點就是重復的數字return slow;}
};

?

?