136-只出现一次的数字思路异或初始为3则变成二进制为011 两个相同的数字异或为0按照题目要求22相同只有一个不同还要取这一个则就用异或4^2^3^2^34class Solution { public int singleNumber(int[] nums) { int result0; for(int num:nums){ result^num; } return result; } }169-多数元素摩尔投票法思路选数量过半的元素采用temp来临时接元素初始判断是否为0并赋值每遍历一个就对比相同就不同就抵消--注意返回值是返回元素不是返回数量class Solution { public int majorityElement(int[] nums) { int temp0; int count0; for(int num:nums){ if(count0){ tempnum; } if(tempnum){count;} else{count--;} } return temp; } }75-颜色分类三指针、荷兰国旗算法思路三指针荷兰国旗算法如果nums[i] 0交换nums[i]和nums[left]lefti如果nums[i] 2交换nums[i]和nums[right]right--注意i 不移动因为换过来的数还没检查如果nums[i] 1i循环条件i rightright 之后都是 2不需要检查注意2时i不需要 因为开始就在左边换左时才加换右时不占位置class Solution { public void sortColors(int[] nums) { int i0; int left0; int rightnums.length-1; while(iright){ 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; tempnums[i]; nums[i]nums[j]; nums[j]temp; } }31-下一个排列思路从右向左找到第一个升序对(i, i1)即nums[i] nums[i1]。然后在[i1, 结束]中找到比 nums[i] 大的最小的数交换它们最后将[i1, 结束]反转成升序。步骤从右向左找到第一个i满足nums[i] nums[i1]如果找不到整个数组降序直接反转整个数组从右向左找到第一个j满足nums[j] nums[i]j i交换nums[i]和nums[j]反转[i1, n-1]部分使其升序注意选升序后面比 nums[i] 大的最小的数不需要min之类的因为能找到升序 说明后面都是降序排列则从最右找 第一个就是注意翻转的传参tempi1就行不能在局部取相关i和j 必须用专门的暂存值来取class Solution { public void nextPermutation(int[] nums) { int nnums.length; int tempi-1; int tempj-1; for(int in-2;i0;i--){ //找右边第一个升序 if(nums[i]nums[i1]){ tempii; break; } } if(tempi0){//若升序存在 for(int jn-1;jtempi;j--){ //若升序存在找大于i的里面最小数 if(nums[j]nums[tempi]){//升序部分之后 一定是降序因此从最右边选就行 tempjj; break; } } swap(nums,tempi,tempj); } reverse(nums,tempi1,n-1);//否则翻转tempi之后整个数组 } public void swap(int[] nums,int i, int j){ int temp0; tempnums[i]; nums[i]nums[j]; nums[j]temp; } public void reverse(int[] nums,int i,int j){ while(ij){ 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 slownums[0]; int fastnums[nums[0]]; //fast二倍速 while(slow!fast){ //slow和fast相遇则停止 slownums[slow]; fastnums[nums[fast]]; } slow0; //slow回到起点fast还是相遇点 while(slow!fast){//再次相遇就是入口 slownums[slow]; fastnums[fast]; } return slow;//slow和fast都可以 } }
