概述
136.只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
解题思路：
位运算。位运算的4个基本性质：
1. 交换律A^B = B^A
2. 结合律A^B^C = A^C^B
3. A^0=A
4. A^A=0
这就使得，数组中所有元素异或之后，个数为偶数的元素会全部抵消，剩下的就是那个单个元素。注意：这题的前提条件是那个单个元素必然存在。其实这个算法不仅使用与两个元素中找单个元素，4,6,8.。。等偶数个元素中找单个元素一样适用。
| class Solution { public: int singleNumber(vector<int>& nums) { for (int i = 2; i <= int(nums.size()); i++) nums[i - 1] ^= nums[i - 2]; return nums[int(nums.size()) - 1]; } }; |
137.只出现一次的数字II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2] 输出: 3
示例 2:
输入: [0,1,0,1,0,1,99] 输出: 99
解题思路：
位运算（左移>>,右移<<）。很显然，136解决了偶数问题，137就会出现奇数元素中查找单个元素。以下这个方法适用于N（N>=2）元素中，查找唯一的单个元素。
1.将数字转换成二进制数字。
2.统计每个位上出现1的个数。
3.很显然，如不考虑单个元素，32位上的1的个数都是N的倍数，也就意味着那个单元素会使得有些位出现%N == 1。
| class Solution { public: int singleNumber(vector<int>& nums) { vector<int> data(32, 0); int size = nums.size(), i, j; for (i = 1; i <= size; i++) { for (j = 1; j <= 32; j++) { data[j - 1] += nums[i - 1] & 1; nums[i-1]=nums[i-1] >> 1; if (nums[i - 1] == 0) break; } } int result = 0; for (i = 1; i <= 32; i++) { result |= (data[i - 1] % 3) << (i - 1); } return result; } }; |
最后
以上就是知性小白菜为你收集整理的Leetcode:136.只出现一次的数字&&Leetcode:137.只出现一次的数字II的全部内容，希望文章能够帮你解决Leetcode:136.只出现一次的数字&&Leetcode:137.只出现一次的数字II所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复