问题描述
算法 Algorithms （第四版）书中，第1章：基础编程模型第15题：
结果：
- 编写一个静态方法 histogram(), 接受一个整型数组a[] 和一个整数M为参数，并返回一个大小为M的数组。
条件：
- 其中第i个元素的值为整数i在参数数组中出现的次数。
- 如果a[]中的值均在0到M-1之间，返回数组中所有元素之和应该和a.length相等
问题解答
第一步：定义静态函数 histogram(int[] a, int m)
public static int[] histogram(int[] a, int m) { int[] nm = new int[m]; int sum = 0; for (int i = 0; i < m; i++) { nm[i] = countValueTimes(a, i); //计算第i个元素的值为整数i在参数数组中出现的次数 sum += nm[i]; //计算新数组中所有元素之和 } //判断数组中所有元素之和应该和a.length相等 if (sum == a.length) { System.out.println(" == == Match result is: " + outputArraytoString(nm)); return nm; } else return nm; }
第二步：实现计算整形数组 a[] 中出现整数i的次数
public static int countValueTimes(int[] a, int x) { if (a.length <= 0) return 0; int count = 0; for (int i = 0; i < a.length; i++) { if (a[i] == x) count++; } return count; }
第三步：创建辅助函数 outputArraytoString，把整型数组输出为字串打印在屏幕中
public static String outputArraytoString(int[] a) { String result = ""; for (int i = 0; i < a.length; i++) { result += a[i] + " "; if (i > 0 && i % 10 == 0) result += "\n"; } return result; }
第四步：准备执行90次的startRun函数和初始化整型数组 a[]
// 开始执行 histogram 函数，运行90次，看有多少次结果匹配1，2两个条件 public static void startRun() { for (int i = 10; i < 100; i++) { System.out.println("Start for length " + i); int[] originala = initArrayInt(i); System.out.println("the original array is: " + outputArraytoString(originala)); int[] newintarray = histogram(originala, i); System.out.println("new array int is: " + outputArraytoString(newintarray)); } } public static int[] initArrayInt(int m) { // 随机生成一个整型数组，大小为M int[] a = new int[m]; Random r = new Random(); for (int i = 0; i < m; i++) { a[i] = r.nextInt(m - 1); } return a; }
第五步：输出结果
== == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == == Start for a[] length is 99 The original array is: 97 47 78 18 23 5 84 94 78 57 22 36 52 78 59 65 27 80 46 65 37 80 0 42 66 39 60 75 62 56 13 38 25 79 80 97 21 72 69 54 5 66 85 58 29 5 27 39 49 38 80 51 61 80 78 74 80 80 1 82 84 55 83 51 26 85 63 5 63 82 72 10 7 8 36 41 75 18 57 42 97 88 95 55 62 52 4 87 59 6 75 23 80 64 34 9 32 60 22 ==== New array Match Condition ==== 1 1 0 0 1 4 1 1 1 1 1 0 0 1 0 0 0 0 2 0 0 1 2 2 0 1 1 2 0 1 0 0 1 0 1 0 2 1 2 2 0 1 2 0 0 0 1 1 0 1 0 2 2 0 1 2 1 2 1 2 2 1 2 2 1 2 2 0 0 1 0 0 2 0 1 3 0 0 4 1 8 0 2 1 2 2 0 1 1 0 0 0 0 0 1 1 0 3 0
运行效果如下：
[END]
