首页 > 代码库 > [LeetCode] Single Number
[LeetCode] Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路一：用一个长度为32的vector<int>存储数组中每个元素中各个位上1出现的次数，然后进行模2操作。
结果为1，则表明这一位是在所要寻找的元素中也为1。
时间复杂度O(32*n),空间复杂度O(1)
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 vector<int> bitnum(32, 0); 5 int res = 0; 6 for (int i = 0; i < 32; ++i) { 7 for (int j = 0; j < n; ++j) { 8 if (A[j] & (1 << i)) { 9 ++bitnum[i];10 }11 }12 res += (bitnum[i] % 2)<<i;13 }14 15 return res;16 }17 };
此方法有较大的通用性，如果序列所有元素出现次数为k,只有一个元素出现一次。那么就把2改为k即可。
思路2：运用异或(^)操作符的性质：两个相同的数异或后结果为0。那么对于A,B,C,D,A,B,C，则有A^B^C^D^A^B^C=D。0^X = X。
时间复杂度O(n), 空间复杂度O(1)
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 int res = 0; 5 6 for (int i = 0; i < n; ++i) { 7 res ^= A[i]; 8 } 9 10 return res;11 }12 };
[LeetCode] Single Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。