面试题56-I：数组中数字出现的次数（C++）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题56-I：数组中数字出现的次数（C++），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2769字，纯文字阅读大概需要4分钟。
内容图文
题目地址：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
题目描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题目示例
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
解题思路
哈希表：初看这道题目，发现又是计数问题，对于计数问题，哈希表是一种很方便的方法，在这里我们使用哈希表arr计数nums数组中的每个元素出现的次数，对出现一次的元素，我们将它存入到数组res中，最后返回res即可，不过空间复杂度不满足O(1)要求。
位运算(异或)：首先要明确异或的含义，异或顾名思义就是两者相同，则异或结果为0，否则结果为1，简言之，n^n=0，n^m=1，需要注意的是任何数与0异或结果为它本身，即n^0=n。回归到本题，出来2个数出现了一次之外，其余数均出现了两次。分析题目，如果除了一个数出现一次外，其余数字出现的次数均出现的次数为2次，那么这个元素如何求呢？不难发现，只要我们遍历数组全员异或一下即可得到，这是因为异或运算具有交换率，两两相同的元素异或结果必然为0，这样最后就只剩下出现一次的那个元素了。对于两个出现一次的元素求解，我们可以采用二进制的方法将所有元素分成两组，使得两个只出现一次的元素在不同的组中，以及相同的元素被分配到相同的组中，然后对两个组分别进行异或运算，即可得到两个只出现一次的元素。其中，我们假设两个只出现一次的元素分别为a和b，那么所有元素异或的结果就是a和b的异或结果。
程序源码
哈希表
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
if(nums.size() == 0) return {};
unordered_map<int, int> arr;
vector<int> res;
for(int i = 0; i < nums.size(); i++)
{
arr[nums[i]] += 1;
}
for(int i = 0; i < nums.size(); i++)
{
if(arr[nums[i]] == 1)
res.push_back(nums[i]);
}
return res;
}
};
异或运算
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
if(nums.size() == 0) return {};
int number = 0; //异或结果
vector<int> res(2, 0);
for(int i = 0; i < nums.size(); i++)
{
number ^= nums[i]; //全员异或得到两个只出现一次元素的异或结果number，其中number的二进制值至少包含一个1，否则，结果就是0，表明两元素相同，与题意不符
}
int pos = number & (-number); //按位与&，找到number最低位起第一个1的位置，，其中，-number表示number的相反数，即取反加1，例pos=(010&(110))=010，而与运算只有当两者均为1是结果才为1，否则为0，即0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1。
for(int i = 0; i < nums.size(); i++) //以pos为标准分组，这个位置是1的数字，放到第一个数组里做异或运算，不是1的放到第二组。
{
if((nums[i] & pos) == pos) res[0] ^= nums[i]; //这个位置是1的时候，放入第一个数组做异或运算
else
res[1] ^= nums[i];
}
return res;
}
};
参考文章
内容总结
以上是互联网集市为您收集整理的面试题56-I：数组中数字出现的次数（C++）全部内容，希望文章能够帮你解决面试题56-I：数组中数字出现的次数（C++）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。