个人博客地址: https://yangyuanlin.club/
欢迎来踩~~~~
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?
題目大意: 给一个数组, 数组中只有一个数是单独出现的, 别的数都是成对出现的, 找出这个单独出现的数. 特别提示: 你的算法应该具有线性的运行复杂度, 而且不要用额外的内存.
思路: 如果没有特别提示的话, 是很好做的: 从第一个数找起, 记录下标, 找到跟它相等的, 就把两个数都置为 0(假设整数中没有 0), 最后数组中没有置为 0 的数就是要找的那个单数. 但是有了这个特别提示, 就要想别的办法, 最后的办法是用位运算, 具体是用异或运算.
异或的运算法则:(1) 异或满足交换律; (2) 相同两个数异或为 0;(3)0 异或一个数为那个数本身.
代码:
- #include<iostream>
- using namespace std;
- int singleNumber(int A[], int n)
- {
- int num = 0;
- for(int i = 0; i < n; i++)
- {
- num ^= A[i];
- }
- return num;
- }
- int main()
- {
- int A[] = {1, 1, 2, 2, 3, 3, 4};
- cout<<singleNumber(A, 7)<<endl;
- return 0;
- }
以上.
来源: http://www.jianshu.com/p/cad05ba0da41