面试题56 |
您所在的位置：网站首页 › 数组统计数字出现次数 › 面试题56 |
|
题目地址：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 singleNumbers(vector& nums) { if(nums.size() == 0) return {}; unordered_map arr; vector 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 singleNumbers(vector& nums) { if(nums.size() == 0) return {}; int number = 0; //异或结果 vector 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; } };参考文章 https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/ https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-56-shu-zu-zhong-shu-zi-chu-xian-de-ci-/ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |