1.题目:
2.我的代码:
C++:
class Solution {
public:// 使用位操作vector<int> singleNumber(vector<int>& nums) {int pos = 0;int mix = 0;for (auto temp : nums){mix ^= temp;}for (pos = 0; pos < 32; ++pos){if (((mix >> pos) & 1) == 1){break;}}cout << pos;vector<int> v;v.resize(2, 0);for (auto temp : nums){if (((temp >> pos) & 1) == 0){v[0] ^= temp;}else{v[1] ^= temp;}}return v;}
};
Java:
class Solution {// Set和Map都可以public int[] singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();int[] ret = new int[2];for (int temp : nums) {if (!set.contains(temp)) {set.add(temp);} else {set.remove(temp);}}int i = 0;for (int temp : nums) {if (set.contains(temp)) {ret[i] = temp;++i;}}return ret;}
}
3.答案代码:
C++:
/*解法一 排序法*思路:* 1. 从前往后遍历,若出现两次,则为相同元素,索引加2* 2. 若出现一次(前后不等),则为所需要的数,存入vector,索引加1* 3. 若没到尾后位置,说明最后一个元素为出现一次的数*/class Solution {public:vector<int> singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());vector<int> res;int i = 0;for ( ; i < nums.size() - 1; ) {if (nums[i] == nums[i + 1]) {i += 2;} else {res.push_back(nums[i]);i += 1;}}if (i < nums.size()) {res.push_back(nums[i]);}return res; }};/*解法二 异或解法*思路:* 1. 只有两个元素出现一次,其它的元素都出现两次.* 2. 全部元素异或消掉出现两次的数字. 异或的结果为s.* 3. 寻找s的lowbit值. lowbit(s)为s的二进制表达式中最右边的1所对应的值. 因此lowbit(s)二进制表达式中只 有一个bit 1. lowbit(s) = s & -s* 4. 用lowbit(s)将数组分成两组. 一组中,元素A[i] & lowbit(s) == lowbit(s), 即包含lowbit(s)的bit 1. 剩余的是另一组.而且,两个不同数也一定分在不同组. 因为异或值s中的bit1就是 因为两个数字的不同而贡献的.* 5. 同一组的元素再异或求出不同数字. 出现两次的数字, 肯定出现同一组, 异或后消除掉.*/class Solution {public:vector<int> singleNumber(vector<int>& nums) {const int N=nums.size();int s = 0;for(auto x : nums){s ^=x;}int lowbit = s & -s;int a=0,b=0;for(auto x:nums){if((x & lowbit) == lowbit){a^=x;}else{b^=x;}}return vector<int>{a,b};}};
Java: