【技巧】【简单/中等】只出现一次的数字/多数元素/颜色分类/下一个排列/寻找重复数

1.只出现一次的数字

原题链接

• 位运算 XOR（异或）
  • 自己和自己异或等于 0。a ^ a = 0
  • 任何数字和 0 异或等于自己。a ^ 0 = a
  • 异或满足交换律和结合律。a ^ b = b ^ a，(a ^ b) ^ c = a ^ (b ^ c)
• 例如[4,1,2,1,2]，把所有数字异或：4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4

publicintsingleNumber(int[]nums){intres=0;for(intnum:nums){res^=num;}returnres;}

2.多数元素

原题链接

• 摩尔投票算法
• nums = [2,2,1,1,1,2,2] 统计结果：2 出现 4 次、1 出现 3 次。不同数字两两抵消，2和1 相互抵消，最终剩下2
• 维护两个变量：
  • candidate // 当前候选数字
  • count // 当前候选数字的票数，count == 0，说明之前的候选人已经被抵消。重新选择当前数字。当前数字等于 candidate 票数增加；当前数字不等于 candidate 票数减小。

publicintmajorityElement(int[]nums){intcandidate=0;intcount=0;for(intnum:nums){if(count==0){candidate=num;}if(num==candidate){count++;}else{count--;}}returncandidate;}

3.颜色分类

原题链接

• 三指针一次遍历,最终得到的标签范围如下

[0, p0)全是0[p0, i)全是1[i, p2]待处理区域(p2, n-1]全是2

- p0：表示 0 区域的右边界，初始为 0 - i：当前遍历位置，初始为 0 - p2：表示 2 区域的左边界，初始为 n - 1

• 如果 nums[i] == 0，和 p0 位置交换，p0++，i++
• 如果 nums[i] == 1，直接 i++
• 如果 nums[i] == 2，和 p2 位置交换，p2–
• 注意：i 不增加，因为从后面换过来的数字还没有检查

nums=[2,1,2,1,0,0]初始i=0、p0=0,p2=5nums[0]=2,交换nums[0]和nums[5],p2--[0,1,2,1,0,2]nums[0]=0,交换nums[0]和nums[0],p0++,i++[0,1,2,1,0,2]nums[1]=1,直接i++[0,1,2,1,0,2]nums[2]=2,交换nums[2]和nums[4],p2--[0,1,0,1,2,2]nums[2]=0,交换nums[0]和nums[1],p0++,i++[0,0,1,1,2,2]nums[3]=1,i++[0,0,1,1,2,2]i=4>p2=3，循环结束

publicvoidsortColors(int[]nums){intn=nums.length;intp0=0;// 0 区域右边界inti=0;// 当前遍历位置intp2=n-1;// 2 区域左边界while(i<=p2){if(nums[i]==0){swap(nums,i,p0);p0++;i++;}elseif(nums[i]==1){i++;}else{// nums[i] == 2swap(nums,i,p2);p2--;// 这里不能 i++，因为换过来的元素还没判断}}}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}

4.下一个排列

原题链接

找到字典序中刚好比当前排列大的最小排列

[1,2,3]->[1,3,2][1,3,2]->[2,1,3][3,2,1]->[1,2,3]//从右往左看，如果数组一直是降序的,例如[3,2,1],没有下一个更大的排列了。所以我们要从右往左找到第一个升序的位置[1,2,3]

• 从右向左，寻找最右侧的第一个升序位置，比如数组[1,3,2,5,4]，需要进行替换的位置是2，因为对于2来说，它后面有比自己较大的数字，应从中选择一个最小的来进行替换，剩余的数进行升序排列。
  • （如果此时是[1,3,2,4,5]，这样第一个升序就是4这个位置）
• 寻找到后，此时右侧位置上全是逐渐降序的数字列，需要找到比 a[i] 大的最小数字然后进行交换，交换后右半部分还是递减的，然后将右半部分进行翻转（从小到大）

nums=[1,3,2,5,4]寻找到最右侧递减的位置为2,i=2=》寻找要交换的数字位置 所以： i=2nums[i]=2=》寻找交换数字的位置 在 i 后面寻找第一个比 nums[i]大的数字：13254↑4>2所以： j=4nums[j]=4=》交换 nums[i]和 nums[j]：13254↘ ↙13452=》反转 i 后面的数组[1,3,4,2,5]

publicvoidnextPermutation(int[]nums){//从右向左寻找第一个非递减的元素位置inti=nums.length-2;for(;i>=0;i--){if(nums[i]<nums[i+1]){break;}}//如果位置为-1,就直接翻转整个数组if(i!=-1){//从右向左寻找第一个大于nums[i]的元素位置for(intj=nums.length-1;j>i;j--){if(nums[j]>nums[i]){swap(nums,i,j);break;}}}//将i+1到nums.length-1的元素反转reverse(nums,i+1,nums.length-1);}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}privatevoidreverse(int[]nums,intleft,intright){while(left<right){swap(nums,left,right);left++;right--;}}

5.寻找重复数

原题链接

• 直接用HashSet也可以，但是要求只用常量级 O(1) 的额外空间

publicintfindDuplicate(int[]nums){Set<Integer>set=newHashSet<>();for(intnum:nums){if(set.contains(num)){returnnum;}set.add(num);}return-1;}

• 快慢指针，把数组看成一个链表，重复数字就是链表的环入口。

nums=[1,3,4,2,2]index->value index:01234value:134220->1->3->2->4->2->4->... 最终重复数字就是环的入口 因为必然出现两个位置指向同一个节点，例如 nums[3]=2nums[4]=2表示3->2、4->2即为环节点

publicintfindDuplicate(int[]nums){//快慢指针intslow=nums[0];intfast=nums[0];// 第一次：快慢指针找相遇点do{slow=nums[slow];fast=nums[nums[fast]];}while(slow!=fast);// 第二次：寻找入口// 从头开始，每次走一步，直到再次相遇slow=nums[0];while(slow!=fast){slow=nums[slow];fast=nums[fast];}returnslow;}