首页 > ACM题库 > LeetCode > LeetCode-Single Number[数组]
2014
11-19

LeetCode-Single Number[数组]

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?

标签: Hash Table Bit Manipulation
分析

异或,不仅能处理两次的情况,只要出现偶数次,都可以清零。

代码1

// LeetCode, Single Number
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int singleNumber(int A[], int n) {
        int x = 0;
        for (size_t i = 0; i < n; ++i)
            x ^= A[i];
        return x;
    }
};

代码2

// LeetCode, Single Number
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int singleNumber(int A[], int n) {
        return accumulate(A, A + n, 0, bit_xor<int>());
    }
};

相关题目

Single Number II


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c