找单数
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：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
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< - 以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！