数组_3

Posted on | In | Visitors:

7. 数组中只出现一次的数字

问题描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现了一次的数字。要求时间复杂度是 O(n)。空间复杂度是 O(1)。
例如：
输入数组 {2， 4， 3， 6， 3， 2， 5， 5}，
输出 4 和 6

思路：

  • 用位运算实现。任何一个数字异或它自己都等于零。如果将所有数字相异或，则最后的结果肯定是，那两个只出现一次的数字异或的结果。

所以：

  • 根据异或的结果1所在的最低位，把数字分成两半，每一半里都还有只出现一次的数据和成对出现的数据。

  • 这样继续对每一半相异或，则可以分别求出两个只出现一次的数字。

例如：

  • 输入数组 {2， 4， 3， 6， 3， 2， 5， 5}。当依次对数组中的每个数字做异或运算之后，得到的结果用二进制表示是 0010。

  • 异或得到的结果中，1 所在的最低位是倒数第二位。于是根据倒数第二位是不是 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
/*
 * num1,num2分别为长度为1的数组。传出参数
 * 将num1[0],num2[0]设置为返回结果
 */
public class FindNumsAppearOnce {
	public void findNumsAppearOnce (int [] array, int num1[], int num2[]) {
		if (array == null || array.length < 2)
			return;
		//对输入数组依次异或
		int resultExclusiveOR = 0;
		for (int i = 0; i < array.length; i++)
			resultExclusiveOR ^= array[i];
		//找出1所在的最低位
		int indexOf1 = findFirstBitIs1(resultExclusiveOR);
		//根据 indexOf1 位是否为1，将原始数组分为两个子数组
		for (int i = 0; i < array.length; i++)
		{
			if (isBit1(array[i], indexOf1))
				num1[0] ^= array[i];
			else
				num2[0] ^= array[i];
		}
	}
	public int findFirstBitIs1(int num) {
		int indexBit = 0;
		while (((num & 1) == 0) && ((indexBit) < 8 * 4))
		{
			num = num >> 1;
			++ indexBit;
		}
		return indexBit;
	}
	public boolean isBit1(int num, int indexBit) {
		num = num >> indexBit;
		return (num & 1)==1;
	}
}

8. 数组中重复的数字

问题描述：

在一个长度为 n 的数组里，所有的数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不值得每个数字重复了多少次。
请找出数组中任意一个重复的数字。

例如：如果输入长度为 7 的数组 {2， 3， 1， 0， 2， 5， 3}
那么对应的输出是重复的数字 2 或者 3。

思路：

注意到，数组长度为 n，数组中数字都在 0 到 n-1 范围内。

  1. 重排这个数组 array，从头到尾依次扫描。

  2. 当扫描到第 i 位时， 比较 array[i] 是否等于 i；

  3. 如果相等，接着扫描下一个数字；

  4. 如果不等，将 array[i] 与 第 array[i] 个数字比较。如果相等，就找到了一个重复的数字。如果不等，将 array[i] 与 第 array[i] 个数字互换位置；

  5. 这样 array[i] 就到了属于它的位置（值与下标相等）。然后重复这个比较、交换的过程。

代码：

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
/*
 * duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
 * Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
 * 这里要特别注意~返回任意重复的一个，赋值duplication[0]
 * Return value:       true if the input is valid, and there are some duplications in the array number
 * otherwise, false
 */
public class Duplicata {
	public boolean duplicata (int numbers[], int length, int [] duplication) {
		if (numbers == null || length <= 0)
			return false;
		for (int i = 0; i < length; i++)
		{
			if (numbers[i] < 0 || numbers[i] > length - 1)
				return false;
		}
		for (int i = 0; i < length; i++)
		{
			while (numbers[i] != i)
			{
				if (numbers[i] == numbers[numbers[i]])
				{
					duplication[0] = numbers[i];
					return true;
				}
				else
				{
					int temp = numbers[i];
					numbers[i] = numbers[temp];
					numbers[temp] = temp;
				}
			}
		}
		return false;
	}
}

分析：

  • 代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是 O(n)。

  • 所有的操作步骤都是在输入数组中进行的，不需要额外分配内存，因此空间复杂度是 O(1)。

9. 构建乘积数组

问题描述：

给定一个数组 A[0，1，…，n-1]，请构建一个数组 B[0，1，…，n-1]，其中 B 中的元素 B[i] = A[0] A[1] … A[i-1] A[i+1] … A[n-1]。
不能使用除法。

思路：

  1. 计算数组 A 中，前 i-1 个元素的乘积，及后 n-i 个元素的乘积。这可以用动态规划实现；
  2. 计算 B[i] 的值。
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
import java.util.ArrayList;
public class Multiply {
    public int[] multiply(int[] A) {
        
		int n = A.length;
		int[] forward = new int[n];
		int[] backward = new int[n];
		int[] B = new int[n];
		forward[0] = 1;
		backward[0] = 1;
		for (int i = 1; i < n; i++)
		{
			forward[i] = A[i - 1] * forward[i - 1];
			backward[i] = A[n - i] * backward[i - 1];
		}
		for (int i = 0; i < n; i++)
		{
			B[i] = forward[i] * backward[n - 1 - i];
		}
		return B;
	}
}