首页 > 代码库 > 【leetcode】Single Number (Medium) ☆

【leetcode】Single Number (Medium) ☆

题目:

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(n^2)的方法,都超时,后来突然顿悟了。异或可以消掉两个相同数字。

直接把所有数字异或在一起,就是单独的那个数字了。

#include <iostream>#include <vector>#include <algorithm>using namespace std;class Solution {public://异或可以把两个相同的数字消除 O(n) AC    int singleNumber3(int A[], int n) {        int ans = 0;        for(int i = 0; i < n; i++)        {            ans ^= A[i];        }        return ans;    }};int main(){    Solution s;    int a[9] = {0,0,1,1,2,3,2,3,4};    int n = s.singleNumber3(a, 9);    return 0;}

 

【leetcode】Single Number (Medium) ☆