现在的位置: 首页 > 综合 > 正文

leetCode解题报告之SingleNumberI,II(知识点:位运算)

2014年09月05日 ⁄ 综合 ⁄ 共 822字 ⁄ 字号 评论关闭

由于两题是姐妹题,所以放在同一个博文里了!


题目1:

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?


题目2:

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

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


不知道这个题目如何做分析和讲解,直接上AC代码,欢迎留言指点


public class SingleNumber {
	/* 简单的异或操作的处理!
	 * 一个数组中只有一个数字出现了一次,其余都出现过两次,找出这个出现一次的数字
	 * */
	public int singleNumber1(int[] A) {
        int result = 0;
        for (int i=0; i<A.length; ++i){
        	result ^= A[i];
        }
		return result;
    }
	
	/* 
	 * 一个数组中只有一个数字出现了一次,其余都出现过三次,找出这个出现一次的数字
	 * */
	public int singleNumber2(int[] A) {
        if (A == null) return 0;
        int x0 = ~0, x1 = 0, x2 = 0, t;
        for (int i = 0; i < A.length; i++) {
            t = x2;
            x2 = (x1 & A[i]) | (x2 & ~A[i]);
            x1 = (x0 & A[i]) | (x1 & ~A[i]);
            x0 = (t & A[i]) | (x0 & ~A[i]);
        }
        return x1;
    }
}

抱歉!评论已关闭.