single number

作者: 牵丝笼海 | 来源:发表于2018-07-02 09:35 被阅读5次

给定一个整数数组，除了一个元素外，每个元素都会出现两次。
找到那一个出现一次的元素。
注意：时间复杂度O(n)，空间复杂度O(1)

1.异或满足交换律
2.相同两个数异或为0
3.0异或一个数为那个数本身
将数组所有元素进行异或操作得到的结果即为所求的元素值

int singleNumber(int A[], int n)
{
    int res = A[0];
    for (int i = 1; i < n; ++i)
    {
        res ^= A[i];
    }

    return res;
}

一篇文章搞懂面试中leetcode位操作算法题
Single Number落单的数落单的数 IISingle Number II Single Number I...
single number
题目描述给定一个整数数组，除了一个元素外，每个元素都会出现两次。找到那一个出现一次的元素。注意：时间复杂度O(n...
Single number
用异或
Single Number
题目要求找出在算法的时间复杂度为线性时间，且不占据额外的内存下面讲解算法：该算法主要用到了位运算中的异或运算^,...
Single Number
Single Number 今天是一道有关位运算的题目，来自LeetCode(#136)，难度为Medium，Ac...
Single Number
Problem Given an array of integers, every element appears...
Single Number
Given an array of integers, every element appearstwiceexc...
Single Number
Given an array of integers, every element appearstwiceexc...
Single Number
按位亦或可求解，复杂度为O（n）
Single Number
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single...