您好,欢迎来到伴沃教育。
搜索
您的当前位置:首页[LeetCode]136. Single Number

[LeetCode]136. 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?

题目

给定一个整数数组,里面只有一个数只出现一次,其余的数都出现两次,找出只出现一次的数。

方法

采用异或运算^
a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ (b ^ c)

c代码

#include <assert.h>

int singleNumber(int* nums, int numsSize) {
    int i = 0;
    int single = 0;
    for(i = 0; i < numsSize; i++) {
        single ^= nums[i];
    }
    return single;
}

int main() {
    int nums[5] = {1,3,3,1,5};
    assert(singleNumber(nums, 5) == 5);

    return 0;
}

Copyright © 2019- bangwoyixia.com 版权所有 湘ICP备2023022004号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务