首页 > 代码库 > LeetCode Problem 136:Single Number
LeetCode Problem 136: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?
题目要求O(n)时间复杂度，O(1)空间复杂度。
思路1：初步使用暴力搜索，遍历数组，发现两个元素相等，则将这两个元素的标志位置为1，最后返回标志位为0的元素即可。时间复杂度O(n^2)没有AC，Status:Time Limit Exceed
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 5 vector <int> flag(n,0); 6 7 for(int i = 0; i < n; i++) { 8 if(flag[i] == 1) 9 continue;10 else {11 for(int j = i + 1; j < n; j++) {12 if(A[i] == A[j]) {13 flag[i] = 1; 14 flag[j] = 1;15 }16 }17 }18 }19 20 for(int i = 0; i < n; i++) {21 if(flag[i] == 0)22 return A[i];23 }24 }25 };
思路2：利用异或操作。异或的性质1：交换律a ^ b = b ^ a，性质2：0 ^ a = a。于是利用交换律可以将数组假想成相同元素全部相邻，于是将所有元素依次做异或操作，相同元素异或为0，最终剩下的元素就为Single Number。时间复杂度O(n)，空间复杂度O(1)
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 5 //异或 6 int elem = 0; 7 for(int i = 0; i < n ; i++) { 8 elem = elem ^ A[i]; 9 }10 11 return elem;12 }13 };
LeetCode Problem 136:Single Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。