先上第一题目:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
1.其实如果了解异或的性质的话很容易写出答案
class Solution { public int singleNumber(int[] nums) { int x=0; for(int i=0;i<nums.length;i++){ x=x^nums[i]; } return x; } }
如果没想到异或或者不了解异或(^)的我也把它的性质写一下
1.交换律:a ^ b ^ c <=> a ^ c ^ b
2.任何数于0异或为任何数 0 ^ n => n
3.相同的数异或为0: n ^ n => 0
我们这利用的就算它的2和3的性质,相同的数全部异或以后就为0,而单独剩下的数异或0后不变,所以整个数组异或后剩下的就是我们的答案。
想到遍历的要认真反省一下了。。。。
再来看下进阶的题目:
给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
很容易看出相比之前唯一的变化的数量加多了1,而这恰恰就是为了不能让你直接使用异或操作符,因为即使用了你重复的数字仍然还有1个,但我们依旧可以第一题为基础展开思考。
public static int singleNumber(int[] nums) { int x=nums.length/3; int count=0; Arrays.sort(nums); for(int i=0;i<nums.length-2;i++){ if(nums[i]!=nums[i+1]||nums[i]!=nums[i+2]) { return nums[i] ^ nums[i + 1] ^ nums[i + 2]; } count++; if(count==x) { break; } i+=2; } return nums[nums.length-1]; }
思路:虽然重复数字的数量增加到三个,但我们可以先将数组排成升序,然后将三个三个进行捆绑比较,如果三个一样那么直接进行将i的值加三对下三个进行比较。如果到某组三个数不完全相等,那么也一定有两个数是相等的,这时我们只需要对这三个数进行异或即可得到答案。这种i一次性加3的情况下,很容易栈溢出。由题目可知数组的长度除以3肯定是余1的,所以我们把它对3取整得到它有多少组三个数,同时用计数器count计算已经检验过几组三个数,再检查完后及时跳出循序,此时还没得到答案说明前面每组三个数都相等,说明最后一个单独的数就是答案,只需将它返回即可。
当然力扣上题解里还有大佬们各种厉害的方法,也应该多去学习一下。
3.再次进阶的题目
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
真没做出来哎心累。。。copy了一份答案
思路:
首先利用相同值异或为0的特性,把整个数组进行异或操作,抵消后得到xOy
接下来我们要利用xOy这个异或结果,拆分出x和y具体的数值
假设xOy的值为0010,根据异或的特点,同一位相同为0,不相同为1,也就是说x和y在异或结果为1的这一位上(即第二个位置)不同
根据第四点,我们先对xOy进行移位查找,找到结果为1的位div
然后我们重新遍历数组,对每一个数进行分组,将div这一位数值分别为0和1的数字分为两组(相同数值每一位都相同,会分到同一组,而唯一的两个数字这一位不同,会被分到两组)
当两组异或操作结束,相同的数字被抵消掉,两组剩下的结果值就是我们要找的两个唯一值
class Solution { public int[] singleNumber(int[] nums) { int ret = 0; for (int n : nums) { ret ^= n; } int div = 1; while ((div & ret) == 0) { div <<= 1; } int a = 0, b = 0; for (int n : nums) { if ((div & n) != 0) { a ^= n; } else { b ^= n; } } return new int[]{a, b}; } }
对二进制不熟根本理解不了分组只能流泪