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) 4publicintsingleNumber(int[]nums){intres0;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){intcandidate0;intcount0;for(intnum:nums){if(count0){candidatenum;}if(numcandidate){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 位置交换p0i如果 nums[i] 1直接 i如果 nums[i] 2和 p2 位置交换p2–注意i 不增加因为从后面换过来的数字还没有检查nums[2,1,2,1,0,0]初始i0、p00,p25nums[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]i4p23循环结束publicvoidsortColors(int[]nums){intnnums.length;intp00;// 0 区域右边界inti0;// 当前遍历位置intp2n-1;// 2 区域左边界while(ip2){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){inttempnums[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,i2》寻找要交换的数字位置 所以 i2nums[i]2》寻找交换数字的位置 在 i 后面寻找第一个比 nums[i]大的数字13254↑42所以 j4nums[j]4》交换 nums[i]和 nums[j]13254↘ ↙13452》反转 i 后面的数组[1,3,4,2,5]publicvoidnextPermutation(int[]nums){//从右向左寻找第一个非递减的元素位置intinums.length-2;for(;i0;i--){if(nums[i]nums[i1]){break;}}//如果位置为-1,就直接翻转整个数组if(i!-1){//从右向左寻找第一个大于nums[i]的元素位置for(intjnums.length-1;ji;j--){if(nums[j]nums[i]){swap(nums,i,j);break;}}}//将i1到nums.length-1的元素反转reverse(nums,i1,nums.length-1);}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}privatevoidreverse(int[]nums,intleft,intright){while(leftright){swap(nums,left,right);left;right--;}}5.寻找重复数原题链接直接用HashSet也可以但是要求只用常量级 O(1) 的额外空间publicintfindDuplicate(int[]nums){SetIntegersetnewHashSet();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){//快慢指针intslownums[0];intfastnums[0];// 第一次快慢指针找相遇点do{slownums[slow];fastnums[nums[fast]];}while(slow!fast);// 第二次寻找入口// 从头开始每次走一步直到再次相遇slownums[0];while(slow!fast){slownums[slow];fastnums[fast];}returnslow;}
【技巧】【简单/中等】只出现一次的数字/多数元素/颜色分类/下一个排列/寻找重复数
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) 4publicintsingleNumber(int[]nums){intres0;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){intcandidate0;intcount0;for(intnum:nums){if(count0){candidatenum;}if(numcandidate){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 位置交换p0i如果 nums[i] 1直接 i如果 nums[i] 2和 p2 位置交换p2–注意i 不增加因为从后面换过来的数字还没有检查nums[2,1,2,1,0,0]初始i0、p00,p25nums[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]i4p23循环结束publicvoidsortColors(int[]nums){intnnums.length;intp00;// 0 区域右边界inti0;// 当前遍历位置intp2n-1;// 2 区域左边界while(ip2){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){inttempnums[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,i2》寻找要交换的数字位置 所以 i2nums[i]2》寻找交换数字的位置 在 i 后面寻找第一个比 nums[i]大的数字13254↑42所以 j4nums[j]4》交换 nums[i]和 nums[j]13254↘ ↙13452》反转 i 后面的数组[1,3,4,2,5]publicvoidnextPermutation(int[]nums){//从右向左寻找第一个非递减的元素位置intinums.length-2;for(;i0;i--){if(nums[i]nums[i1]){break;}}//如果位置为-1,就直接翻转整个数组if(i!-1){//从右向左寻找第一个大于nums[i]的元素位置for(intjnums.length-1;ji;j--){if(nums[j]nums[i]){swap(nums,i,j);break;}}}//将i1到nums.length-1的元素反转reverse(nums,i1,nums.length-1);}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}privatevoidreverse(int[]nums,intleft,intright){while(leftright){swap(nums,left,right);left;right--;}}5.寻找重复数原题链接直接用HashSet也可以但是要求只用常量级 O(1) 的额外空间publicintfindDuplicate(int[]nums){SetIntegersetnewHashSet();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){//快慢指针intslownums[0];intfastnums[0];// 第一次快慢指针找相遇点do{slownums[slow];fastnums[nums[fast]];}while(slow!fast);// 第二次寻找入口// 从头开始每次走一步直到再次相遇slownums[0];while(slow!fast){slownums[slow];fastnums[fast];}returnslow;}
