136-只出现一次的数字
思路：异或，初始为3则变成二进制为011， 两个相同的数字异或为0；按照题目要求，22相同，只有一个不同，还要取这一个，则就用异或
4^2^3^2^3=4
class Solution { public int singleNumber(int[] nums) { int result=0; for(int num:nums){ result^=num; } return result; } }169-多数元素（摩尔投票法）
思路：选数量过半的元素，采用temp来临时接元素，初始判断是否为0并赋值；每遍历一个就对比，相同就++，不同就抵消--
注意：返回值是返回元素，不是返回数量
class Solution { public int majorityElement(int[] nums) { int temp=0; int count=0; for(int num:nums){ if(count==0){ temp=num; } if(temp==num){count++;} else{count--;} } return temp; } }75-颜色分类（三指针、荷兰国旗算法）
思路：三指针（荷兰国旗算法）
如果
nums[i] == 0：交换nums[i]和nums[left]，left++，i++如果
nums[i] == 2：交换nums[i]和nums[right]，right--（注意：i 不移动，因为换过来的数还没检查）如果
nums[i] == 1：i++
循环条件：i <= right（right 之后都是 2，不需要检查）
注意：==2时，i不需要++ ，因为开始就在左边，换左时才加，换右时不占位置
class Solution { public void sortColors(int[] nums) { int i=0; int left=0; int right=nums.length-1; while(i<=right){ if(nums[i]==0){ swap(nums,i,left); left++; i++; }else if(nums[i]==2){ swap(nums,i,right); right--; }else{ i++; } } } public void swap(int[] nums,int i,int j){ int temp; temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } }31-下一个排列
思路：从右向左找到第一个升序对(i, i+1)，即nums[i] < nums[i+1]。
然后在[i+1, 结束]中找到比 nums[i] 大的最小的数，交换它们，最后将[i+1, 结束]反转成升序。
步骤：
从右向左找到第一个
i，满足nums[i] < nums[i+1]如果找不到（整个数组降序），直接反转整个数组
从右向左找到第一个
j，满足nums[j] > nums[i]（j > i）交换
nums[i]和nums[j]反转
[i+1, n-1]部分（使其升序）
注意：选升序后面比 nums[i] 大的最小的数，不需要min之类的，因为能找到升序 说明后面都是降序排列，则从最右找 第一个就是；
注意翻转的传参tempi+1就行；
不能在局部取相关i和j， 必须用专门的暂存值来取；
class Solution { public void nextPermutation(int[] nums) { int n=nums.length; int tempi=-1; int tempj=-1; for(int i=n-2;i>=0;i--){ //找右边第一个升序 if(nums[i]<nums[i+1]){ tempi=i; break; } } if(tempi>=0){//若升序存在 for(int j=n-1;j>tempi;j--){ //若升序存在，找大于i的里面最小数 if(nums[j]>nums[tempi]){//升序部分之后 一定是降序，因此从最右边选就行 tempj=j; break; } } swap(nums,tempi,tempj); } reverse(nums,tempi+1,n-1);//否则翻转tempi之后整个数组 } public void swap(int[] nums,int i, int j){ int temp=0; temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } public void reverse(int[] nums,int i,int j){ while(i<j){ swap(nums,i,j); i++; j--; } } }287-寻找重复数 快慢指针（Floyd 判圈算法）
思路：不用理解直接背
将
nums[i]看作i → nums[i]的指针因为元素范围
[1, n]，不会指向0（不会出界）重复的数意味着有多个索引指向同一个值 → 形成环
步骤：
快慢指针：
slow = nums[0]fast = nums[nums[0]]（快指针一次走两步）
第一次相遇（检测环）：
slow走一步：slow = nums[slow]fast走两步：fast = nums[nums[fast]]相遇时停止
找环的入口（重复的数）：
slow回到起点：slow = 0两个指针都每次走一步
再次相遇的地方就是重复的数
class Solution { public int findDuplicate(int[] nums) { int slow=nums[0]; int fast=nums[nums[0]]; //fast二倍速 while(slow!=fast){ //slow和fast相遇则停止 slow=nums[slow]; fast=nums[nums[fast]]; } slow=0; //slow回到起点，fast还是相遇点 while(slow!=fast){//再次相遇就是入口 slow=nums[slow]; fast=nums[fast]; } return slow;//slow和fast都可以 } }
