由于两题是姐妹题,所以放在同一个博文里了!
题目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; } }