【LeetCode】SingleNumber[I][II] 叁歲伎倆 2022-05-26 05:08 100阅读 0赞 > 题目描述 Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 给定一个整数数组，其中除了一个元素，其他元素均出现了两次，找到那个出现一次的数字 注意：算法只能是线性复杂度，而且不能开辟额外的内存空间 > 思路： > 两个相同的数异或结果为0 > 任何数和0异或的结果是其本身 > 根据上述的两个特性，我们可以得知数组中出现两次的数字经过异或运算后结果为0，同只出现一次的数字异或后的结果就是其本身，也就是整个数组的异或结果就是只出现一次的数字 public class Solution { public int singleNumber(int[] A) { //输入异常返回-1 if(A == null || A.length == 0) return -1; int result = 0; for(int i=0;i<A.length;i++){ result ^= A[i]; } return result; } } > 题目描述 Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 上一个题目的升级版本，给定一个整数数组，其中只有一个元素出现一次，其余元素均出现了3次，寻找只出现一次的元素。 注意：算法时间复杂度为线性，并且不使用额外的空间 > 思路： > 出现三次，那么对于每个出现三次的数字来说，其对应二进制位的相加和必为3或0 > 所以，统计数组中所有元素每一位的和，对3取余。如果出现了三次，那么对3取余必为0，那么最终求得的结果就是出现一次的数字 public class Solution { public int singleNumber(int[] A) { int result = 0; if(A == null || A.length == 0) return -1; //依次求每一位 for(int i=0;i<32;i++){ int bits = 0; //依次求得数组中每个元素的第i位的和 for(int j = 0;j<A.length;j++){ bits += (A[j] >> i)&1; } //出现三次的元素的对3取余为0，那么最终求得的结果就是出现一次的数字 result |= (bits%3) << i; } return result; } } 还有一种更牛的解法，但是并没有看懂。。。。。
还没有评论，来说两句吧...