本文共 1437 字,大约阅读时间需要 4 分钟。
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
要求:时间复杂度为O(n) ,空间复杂度为O(1)描述中,有一个很重要的条件,那就是 , 其余每个元素均出现两次(偶数次也可)
根据这个条件 , 异或运算 ,就可以很轻松的解决这个问题 a ⊕ b = { 0 a = b 1 a != b a \oplus b = \begin{cases} 0& \text{a = b}\\ 1& \text{a != b} \end{cases} a⊕b={ 01a = ba != b 将所有的数进行异或后 , 最终的值就是值出现一次的元素。class Solution { public int singleNumber(int[] nums) { int ans = nums[0]; if (nums.length > 1) { for (int i = 1; i < nums.length; i++) { ans = ans ^ nums[i]; } } return ans; }}
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
要求:时间复杂度为O(n) ,空间复杂度为O(1)和上面的同理可得,只不过这里异或的结果 ,是两个唯一数异或的结果 ,记为 xy
主要的问题是,如何从 xy ,分离出 x 和 y 这两个唯一数 思考 :xy 肯定是非零, 记录 xy 的二进制中 1 出现的最低位位置 ,记为 p 根据 p 将数组划分为 ---- p 位置为 1 和 0 两个组 执行上面的过程,求出 x ( y ) ,通过 x y ⊕ x = y xy \oplus x = y xy⊕x=yclass Solution { public int[] findNumsAppearOnce(int[] nums) { //假设两个唯一的数为x和y //先把所有的数异或一遍,可以得到x ^ y int xy = 0; for(int num : nums){ xy ^= num; } //再找到x ^ y中某一位为1,则x和y在这一位上一定不同(一个是1一个是0) int p = 0; while((xy >> p & 1) == 0) p++; //通过此位将原来所有的数分成两类:此位是1和此位是0(此时x和y各属于一类) //在每一类中找出唯一的那个数 int x = 0; for(int num : nums) if((num >> k & 1) == 1) x ^= num; int y = x ^ xy; int[] res = new int[]{ x, y}; return res; }}
转载地址:http://dhjzz.baihongyu.com/