数组

Posted on | In | Visitors:

1. 旋转数组的最小数字

问题描述：

把一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出该旋转数组的最小元素。
例如：
数组 {3，4，5，1，2} 为 {1，2，3，4，5} 的一个旋转，该数组的最小数字为 1。

思路：

旋转数组可以划分为两个排序的子数组。前面子数组的元素都大于等于后面子数组的元素。最小的元素的分界线。

  1. 用二分查找法的思路，两个指针，分别指向第一个和最后一个元素。

  2. 找到数组的中间元素。Mid = ( p1 + p2 ) / 2；

    • 如果 Mid 大于 p1 指向元素，那么 Mid 在第一个子数组中，最小元素位于其后面。于是让 p1 指向 Mid；
    • 如果 Mid 小于 p2 指向元素，那么 Mid 在第二个子数组中，最小元素位于其前面。于是让 p2 指向 Mid；

  3. p1 总是指向前一个递增数组的元素，p2 总是指向 递增数组的元素。最终 p1指向前一个数组的最后一个元素，p2 指向后一个数组的第一个元素，即最小元素。这是循环结束的条件。

特例：

  1. 如果把排序数组的前面 0 个元素搬运到后面，也是一个旋转数组。此时最小元素就是第一个数字。所以把 indexMid 初始化为 index1。

  2. 当 index1，index2，indexMid 指向的三个数字相等时，只能顺序查找。

代码：

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
public static int Min(int[] numbers) {
	if (numbers == null || numbers.length == 0) {
		return 0;
	}
	int index1 = 0;
	int index2 = numbers.length - 1;
	int indexMid = index1;
	while (numbers[index1] >= numbers[index2]) {
		if (index2 - index1 == 1) {
			indexMid = index2;
			break;
		}
		indexMid = (index1 + index2) / 2;
		//如果 index1，index2，indexMid 指向的三个数字相等，则只能顺序查找
		if (numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1]) {
			return MinInOrder(numbers, index1, index2);
		}
		if (numbers[indexMid] >= numbers[index1]) {
			index1 = indexMid;
		}
		else if (numbers[indexMid] <= numbers[index2]) {
			index2 = indexMid;
		}
	}
	return numbers[indexMid];
}
public static int MinInOrder(int[] numbers, int index1, int index2) {
	int result = numbers[index1];
	for (int i = index1 + 1; i <= index2; i++) {
		if (result > numbers[i]) {
			result = numbers[i];
		}
	}
	return result;
}

2.调整数组顺序使奇数位于偶数前面

问题描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

version1 思路：

  1. 维护两个指针 i 和 j 。第一个指针 i 指向数组第一个元素，第二个指针 j 指向数组最后一个元素；

  2. 如果 i 指向偶数，j 指向奇数，交换这两个数字；

  3. 如果 i 指向奇数，j 指向奇数，后移 i ，直到 i 指向偶数；

  4. 如果 i 指向偶数，j 指向偶数，前移 j，直到 j 指向奇数；

  5. 如果 i 指向奇数，j 指向偶数，则后移 i ，前移 j ，直到到达循环结束条件；

  6. 循环结束条件：第二个指针在第一个指针前面，此时所有奇数都已经在偶数前面了。

version1 代码：

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
public void reOrderArray(int[] arr) {
	if (arr == null || arr.length == 0) {
		return;
	}
	int i = 0;
	int j = arr.length - 1;
	while (i < j) {
		//如果 i 指向偶数，j 指向奇数，交换
		if (isEven(arr[i]) && !isEven(arr[j])) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		// 如果 i 指向奇数，j 指向奇数，后移 i ，直到 i 指向偶数
		else if (!isEven(arr[i]) && !isEven(arr[j])) {
			i++;
		}
		//如果 i 指向偶数，j 指向偶数，前移 j，直到 j 指向奇数；
		else if (isEven(arr[i]) && isEven(arr[j])) {
			j--;
		}
		//如果 i 指向奇数，j 指向偶数，则后移 i ，前移 j ，
		else {
			i++;
			j--;
		}	
	}
} 
public boolean isEven(int n) {
	return (n & 1) == 0;
}

version 1 可以实现把数组中的所有奇数都移到整数的前面，但是不能保证原有次序。例如：

测试用例：[1,2,3,4,5,6,7]
对应输出应该为：[1,3,5,7,2,4,6]
我的输出为：[1,7,3,5,4,6,2]

于是有了 version2。

version2 思路：

要保证原有次序，只能顺次移动或者相邻交换。

  1. i 从左向右遍历，找到第一个偶数；
  2. j 从 i+1 开始向后找，直到找到第一个奇数；
  3. 将 [i, …, j-1] 的元素整体后移一位，最后将找到的奇数放入 i 位置，然后 i++；
  4. 终止条件： j 向后遍历查找失败。

3.数组中出现次数超过一半的数字

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如：输出一个长度为 9 的数组 {1，2，3，2，2，2，5，4，2}。
由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。

思路：

  1. 在遍历数组的时候保存两个值：一个是数组中的数字，一个是次数；

  2. 如果下一个数字和之前保存的数字相同，则次数加一；

  3. 如果下一个数字和之前保存的数字不同，则次数减一；

  4. 如果次数为零，则保存下一个数字，并将次数设为 1；

  5. 验证一下是不是真的出现次数超过数组长度一半。防止有的测试用例不满足要求。

代码：

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
public static int moreThanHalfNum(int[] array) {
	int length = array.length;
	if (array == null || length <= 0) {
		return 0;
	}
	int result = array[0];
	int times = 1;
	for (int i = 1; i < length; i++) {
		if (times == 0) {
			result = array[i];
			times = 1;
		}
		else if (array[i] == result) {
			times++;
		}
		else {
			times--;
		}
	}
	//验证是否真的有出现次数超过数组长度一半的数字
	int frequency = 0;
	for (int i = 0; i < length; i++) {
		if (array[i] == result) {
			frequency++
		}
	}
	if (frequency * 2 <= length) {
		result = 0;
	}
	return result;
}

4.连续子数组的最大和

问题描述：

输入一个整型数组，数组里有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如：
输入：数组为 {1，-2，3，10，-4，7，2，-5}，
则最大的连续子数组为{3，10，-4，7，2}，
输出：该子数组的和 18。

第一种思路：

  1. 从头到尾累加数组中的每个数字，初始化和为 0。
  2. 如果当前和 CurSum 为负值，则不加（加了肯定更小），把 CurSum 直接设为下一数组元素值；
  3. 如果加到某个数值 array[i] 之后，比加 array[i] 之前的和更大，则更新可能的最大和 GreatSum；
  4. 如果加到某个数值 array[i] 之后，比加 array[i] 之前的和要小，则 GreatSum 仍为原值；

第一中解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int findGreatestSumOfSubArray(int[] array) {
	int length = array.length;
	if (array == null || length == 0) {
		return 0;
	}
	int CurSum = 0;  //现在的和
	int GreatSum = 0x80000000;  //指最小的负数
	for (int i = 0; i < length; i++) {
		if (CurSum <= 0) {
			CurSum = array[i];
		}
		else {
			CurSum += array[i];
		}
		if (CurSum > GreatSum) {
			GreatSum = CurSum;
		}
	}
	return GreatSum;
}

第二种思路（动态规划）：

用函数 f(i) 表示以第 i 个数字结尾的子数组的最大和，则：

$$
f(n) =
\begin{cases}
array[i], & \text{i = 0 or f(i - 1) <= 0} \
f(n - 1) + array[i], & \text{i != 0 && f(i - 1) > 0} \
\end{cases}
$$

解答和第一种一样。