数据结构与算法——1125—面试题位运算

1、有一个数字只出现一次

题目

存在一个数组nums，其中有一个数字只出现一次，其余数字均出现偶数次，求出这个出现一次的数字

解答

1、整体异或

2、先排序再比较

时间复杂度O(n*log2n)        空间复杂度O(log2n)

3、计数

把所有数字放入进map或者哈希表中，容器为key——value的存储方式，key是元素，value是这个元素出现的次数，此时遍历容器，找出出现元素为1的即可

如果使用map，时间复杂度为O(n*log2n)        如果使用哈希表，时间复杂度为O(n)

空间复杂度O(n)

4、暴力

顺序的取出数组中的每个元素与其余的每个元素进行比较，查看是否出现过

时间复杂度O(n**2)        空间复杂度O(1)

异或方法详解

遍历一遍，则时间复杂度为O(n)，空间复杂度O(1)

2、位运算

与、位或、按位取反、左移、右移

位或——|：只要有1，结果位1——使用只有一位为1的数字向原数字上进行叠加，叠加特性

异或——^：相异为1，相同为0

位与——&：只要有0，结果为0——检测某一位是否为1

按位取反——~：运算级别非常高

左移<<：左移尾部补0

右移>>：右移头部补与符号位相同的数字

3、逻辑运算符

&&——逻辑与        ||——逻辑或

逻辑运算符比位运算符优先级高，有短路原则

4、把十进制数字转为二进制

使用数字1与要检测的十进制数字进行位与，然后将数字1进行左移

5、有两个元素只出现一次

解答

1、整体异或——循环

2、找到一个非零位——将结果与其负数形式进行位与

3、按照找到的非零位的情况，将数组分为两组

4、各组内进行异或

3-4分组异或可以融合成一步，边循环边异或

代码

#include<iostream>
#include<vector>
using namespace std;void nonzero(vector<int>nums,int& ans0,int& ans1)
{int len = nums.size();if (len == 1 || len == 0){return;}int ans = 0;for (int v:nums)//整体异或{ans ^= v;}ans= ans & (-ans);	//找到非零位for(int v:nums){//分组(ans& v) ? ans0 ^= v : ans1 ^= v;}
}int main()
{vector<int> nums = { 15,2,12,3,15,12,3,6,2,9 };int ans0 = 0;int ans1 = 0;nonzero(nums, ans0, ans1);cout << ans0 << "   " << ans1;return 0;
}