javaee论坛

普通会员

225648

帖子

324

回复

338

积分

楼主
发表于 2017-07-27 16:13:15 | 查看: 1139 | 回复: 1
Given an array of integers, every element appears twice except for one. Find that single one.

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

// 题目意思很简单,一组数,除了一个数,其他数都是两个两个出现的,现在要求找到这个特殊的数// 要求O(N)的时间复杂度,以及不另外使用空间就能返回正确答案// 见识短浅,我未能想出办法,故参考题解,发现可以用异或运算来求解// 那些两两相同的数异或的结果是0,而任何数和0异或,都不变,因此只需要将数组里面的数异或一遍就可以得出答案,代码如下int singleNumber(int* nums, int numsSize) {    for (int i = 1;i < numsSize;i++) {        nums[0] ^= nums[i];    }    return nums[0];}

普通会员

0

帖子

278

回复

288

积分
沙发
发表于 2019-11-03 05:40:05

楼主听话,快到碗里来!

您需要登录后才可以回帖 登录 | 立即注册

触屏版| 电脑版

技术支持 历史网 V2.0 © 2016-2017