首页 > ACM题库 > LeetCode > LeetCode-Single Number[位运算]
2014
03-27

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?

链接:http://oj.leetcode.com/problems/single-number/

大意:给定一个数组,除了一个元素,其它每个元素都出现了两次,找出这个出现一次的元素。时间复杂度O(n), 空间复杂度O(1).

由于时间复杂度和空间复杂度的限制,应该考虑用位运算来解决,也就是运用异或操作。出现一个和出现两次,其实可以推广到出现奇数次和出现偶数次,可以利用异或运算,考虑每一位: 如果出现了两次偶数次 1 或0 ,异或后都为 0.  奇数次的就为1. 因此

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ans = 0;
        for(int i=0; i<n; i++){
		ans ^= A[i];
	    }
	    return ans;
    }
};

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。