136 Single Number


title: Single Number
tags:
- single-number
- No.136
- simple
- boolean-algebra
- bit
- array


Description

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Corner Cases

  • ""
  • "a"
  • ","

Solutions

XOR Operation

XOR operation satisfies the law of association: (a ^ b) ^ c == a ^ (b ^ c)

Besides, since the truth table is:

0 1
0 0 1
1 1 0

Thus all pairs of the same number are reduced to zero.

The running time is O(n) with O(1) space complexity.

class Solution {
    public int singleNumber(int[] nums) {
        int xor = nums[0];
        for (int i=1; i<nums.length; i++) {
            xor = xor ^ nums[i];
        }
        return xor;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,486评论 0 10
  • 2018年6月23日星期六 台风天 有个中文系毕业的朋友是爱好写作的我最大的幸事。然而爱好写作和会写作是不同的概念...
    散月的月阅读 362评论 0 0
  • 生了场小病,在医院住了大半个月。 邻床是个老太太,把她的抽屉打开,一屉的药,高血压、糖尿病、肾炎、护胃等等。每天的...
    inch阅读 158评论 0 1