数组_2

Posted on | In | Visitors:

5.把数组排成最小的数

问题描述：

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出来的所有数字中最小的一个。
例如：
输入数组 {3，32，321}，
则打印出这 3 个数字能排成的最小数字 321323。

思路：

  1. 将整形数组转换成 String 数组 （为了解决大数问题： m 和 n 都在 int 能表达的范围内，但拼起来的数字 mn 和 nm 用 int 表示就有可能溢出了）；
  2. 将 String 数组排序；
  3. 将排好序的字符数组拼接起来。

关键是，制定排序规则。规则如下：

  • 若 mn > nm ，则 m > n；
  • 若 mn < nm ，则 m < n；
  • 若 mn = nm ，则 m = n 。
  • 比如：“3” < “31”，但 “331” > “313”，所以要拼接起来进行比较。

代码：

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
import java.util.*;
public String PrintMinNumber(int[] numbers) {
	int length = numbers.length;
	if (numbers == null || length == 0) {
		return "";
	}
	String[] str = new String[length];
	// StringBuilder 表示的字符串的可变的
	StringBuilder result = new StringBuilder();
	// 将整形变量转换为 String 数组
	for (int i = 0; i < length; i++) {
		// 将整形变量转换为字符串
		str[i] = String.valueOf(numbers[i]); 
	}
	/*
	 * 将 String 数组排序
	 * 两个对象要使用 compareTo 方法比较大小，就必须实现 Comparator 接口的 compare 方法。
	 * sort(str, Comparator)：根据指定的 Comparator 对 str 集合元素进行排序。
	 */
	Arrays.sort(str, new Comparator<String>() {
		public int compare(String s1, String s2) {
			String c1 = s1 + s2;
			String c2 = s2 + s1;
			return c1.compareTo(c2);
		}
	});
	//将排好序的字符串拼接起来
	for (int i = 0; i < length; i++) {
		result.append(str[i]);
	}
	return result.toString();
}

6.数组中的逆序对

问题描述：

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。

思路：

  • 把数组分割成子数组；
  • 统计出子数组内部的逆序对的数目；
  • 统计出两个相邻子数组之间的逆序对的数目；
  • 在统计逆序对的过程中，还需要对数组进行排序。这个排序的过程其实就是归并排序。

归并排序的合并过程。主要是考虑合并两个有序序列时，计算逆序对数。
规则：

  • 对于两个升序序列，设置两个下标：两个有序序列的末尾。
  • 每次比较两个末尾值，如果前末尾大于后末尾值，则有 “后序列当前长度” 的逆序对，否则不构成逆序对；
  • 然后把较大值拷贝到辅助数组的末尾，即最终要将两个有序序列合并到辅助数组并有序。

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
public class InversePairs {
	public static int count(int[] array, int length) {
		if (array == null || length <= 0) {
			return 0;
		}
		//创建辅助数组
		int[] copy = new int[length];
		for (int i = 0; i < length; i++){
			copy[i] = array[i];
		}
		int result = InversePairsCore(array, copy, 0, length - 1);
		return result;	
	}
	//归并排序的合并过程
	public static int InversePairsCore(int[] array, int[] copy, int start, int end) {
		if (start == end) {
			copy[start] = array[start];
			return 0;
		}
		int mid = (end - start) / 2;
		//递归调用
		int left = InversePairsCore(copy, array, start, start + mid);
		int right = InversePairsCore(copy, array, start + mid + 1, end);
		//归并
		int i = start + mid;  // i 初始化为前半段最后一个数字的下标
		int j = end;  // j 初始化为后半段最后一个数字的下标
		int indexCopy = end;
		int count = 0;  //记录相邻子数组间的逆序数
		//每次比较两个末尾值
		while (i >= start && j >= start + mid + 1) {
			//如果前末尾值大于后末尾值，则有“后序列当前长度”个逆序对
			if (array[i] > array[j]) {
				copy[indexCopy--] = array[i--];
				count += j - mid - start;
			}
			//否则不构成逆序对
			else {
				copy[indexCopy--] = array[j--];
			}
		}
		while(i >= start) {
			copy[indexCopy--] = array[i--];
		}
		while(j >= start + mid + 1) {
			copy[indexCopy--] = array[j--];
		}
		return left + right + count;
	}
}