剑指offer面试题56：数组中数字出现的次数（Java 实现）

96 阅读 0 评论 64 点赞

我是靠谱客的博主追寻短靴，这篇文章主要介绍剑指offer面试题56：数组中数字出现的次数（Java 实现），现在分享给大家，希望可以做个参考。

题目一：在一个数组中除了一个数字只出现一次之外，其他数字都出现了2次，请找出那个只出现了一次的数字。
要求：线性时间复杂度O(N)，空间复杂度为O(1)。

思路：用异或运算来解决问题，由于两个相同的数字的异或结果是0，我们可以把数组中的所有数字进行异或操作，结果就是唯一出现的那个数字。

复制代码

1
2
3
4
5
6
7
8
public int FindANumAppearOnce(int[] array){
		int ans = 0;
		
		for(int i=0; i<array.length; i++){
			ans = ans^array[i];
		}
		return ans;
	}

题目二：在一个数组中除了2个数字只出现一次之外，其他数字都出现了2次，请找出两个只出现了一次的数字。
要求：线性时间复杂度O(N)，空间复杂度为O(1)。

思路：从头到尾异或数组中的每个数字，可以得到只出现1次的两个数字的异或结果。从异或结果中，找到右边开始第一个为1的位数，记为n。我们将数组中所有的数字，按照第n位是否为1，分为两个数组。每个子数组中都包含一个只出现一次的数字，其它数字都是两两出现在各个子数组中。那么结合题目一，我们已经得出了答案。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int[] FindTwoNumsAppearOnce(int[] array) throws Exception{
        if(array == null || array.length == 0)
			throw new Exception("无效输入");

		int ans = 0;
		
		//首先计算出数组中所有数组异或的结果
		for(int i=0; i < array.length; i++){
			ans = ans ^ array[i];
		}
		//得到这个异或结果的最右边第一个为1的位数
		int indexOf1 = FindFirstBitIs1(ans);
		
		int num1 = 0;
		int num2 = 0;
		
		//将整个数组按从右边起第indexOf1为是不是1分为两组
		for(int i=0; i < array.length; i++){
			if(IsBit1(array[i], indexOf1) == true){
				num1 = num1 ^ array[i];
			}
			else{
				num2 = num2 ^ array[i];
			}
		}
		int[] result = {num1, num2};
		return result;
	}
	
	//判断一个数从右边算起第index位是不是1
	private boolean IsBit1(int num, int index) {
		num = num >> index;
		return (num&1) == 1? true : false;
	}


	private int FindFirstBitIs1(int num) {
		int index = 0;
		while((num&1) == 0){
			num = num >> 1;
			index++;
		}
		return index;
	}

题目三：在一个数组中除了一个数字只出现一次之外，其他数字都出现了3次，请找出那个只出现了一次的数字。
要求：线性时间复杂度O(N)，空间复杂度为O(1) 。

思路：如果一个数字出现三次，那么他的二进制表示的每一位(0或者1)也出现3次。如果把所有出现3次的数字的二进制表示的每一位都分别相加起来，那么每一位的和都能被3整除。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int FindANumAppearOnce1(int[] array) throws Exception{
		if(array == null || array.length ==0)
			throw new Exception("无效输入");
		
		//定义一个数组来存储数组中每一个数字的32位数的和
		int[] bitSum = new int[32];
		
		//遍历数组
		for(int i=0; i < array.length; i++){
			int bitMask = 1;
			
			//遍历从后往前存储数字的每一位数
			for(int j=31; j >= 0; j--){
				int bit = array[i] & bitMask;
				
				if(bit != 0){
					bitSum[j] = bitSum[j] + bit;
				}
				
				bitMask = bitMask << 1;
			}
		}
		
		int result = 0;
		for(int i=0; i<32; i++){
			result = result + bitSum[i] % 3;
		}
		return result;
	}