1.4.13 # 解答 # 对象的固定开销用 Object 表示。 a. Accumulator 使用 1.2.4.3 节给出的实现。 = int * 1 + double + Object * 1 = 4 * 1 + 8 + 16 * 1 = 32 b. Transaction = string * 1 + Date * 1 + double * 1 + Object * 1 = (40 + 16 + 4 + 4 + 2N) * 1 + (8 + 32) * 1 + 8 * 1 + 16 * 1 = 128 + 2N c. ...
1.4.14 # 解答 # 这里给出暴力方法，将最内侧循环换成二分查找即为优化版本。 代码 # public static class FourSum { /// <summary> /// 输出数组中所有和为 0 的四元组。 /// </summary> /// <param name="a">包含所有元素的数组。</param> public static void PrintAll(long[] a) { var n = a.Length; for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) { for (var k = j + 1; k < n; k++) { for (var l = k + 1; l < n; l++) { if (a[i] + a[j] + a[k] + a[l] == 0) { Console. ...
1.4.15 # 解答 # 由于数组已经排序（从小到大），负数在左侧，正数在右侧。 TwoSumFaster 设最左侧下标为 lo，最右侧下标为 hi。 如果 a[lo] + a[hi] > 0, 说明正数太大，hi–。 如果 a[lo] + a[hi] < 0，说明负数太小，lo++。 否则就找到了一对和为零的整数对，lo++, hi–。 ThreeSumFaster 对于数组中的每一个数 a，ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。 只要在 TwoSumFaster 外层再套一个循环即可。 代码 # /// <summary> /// TwoSum 的快速实现。（线性级别） /// </summary> /// <param name="a">需要查找的数组范围。</param> /// <returns>数组中和为零的整数对数量。</returns> static int TwoSumFaster(int[] a) { var lo = 0; var hi = a.Length - 1; var count = 0; while (lo < hi) { if (a[lo] + a[hi] == 0) { count++; lo++; hi--; } else if (a[lo] + a[hi] < 0) { lo++; } else { hi--; } } return count; } /// <summary> /// ThreeSum 的快速实现。（平方级别） /// </summary> /// <param name="a">需要查找的数组范围。</param> /// <returns>数组中和为零的三元组数量。</returns> static int ThreeSumFaster(int[] a) { var count = 0; for (var i = 0; i < a. ...
1.4.16 # 解答 # 先将数组从小到大排序，再遍历一遍即可得到差距最小的两个数。 排序算法需要消耗 NlogN，具体见 MSDN：Array.Sort 方法 (Array)。 代码 # var a = new[] { 0.1, 0.3, 0.6, 0.8, 0 }; Array.Sort(a); // Nlog(N) 具体见 https://msdn.microsoft.com/zh-cn/library/6tf1f0bc(v=vs.110).aspx 备注部分 var minDiff = double.MaxValue; double minA = 0; double minB = 0; for (var i = 0; i < a.Length - 1; i++) //N { if (a[i + 1] - a[i] < minDiff) { minA = a[i]; minB = a[i + 1]; minDiff = a[i + 1] - a[i]; } } Console. ...
1.4.17 # 解答 # 遍历找到最小值和最大值即可。 代码 # var a = new[] { 0.1, 0.3, 0.6, 0.8, 0 }; double min = int.MaxValue; double max = int.MinValue; for (var i = 0; i < a.Length; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } Console.WriteLine($"MaxDiff Pair: {min} {max}, Max Difference: {Math.Abs(max - min)}");
1.4.18 # 解答 # 和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。 在三个数中比较得到最小值需要两次比较，因此最坏情况下为 $~2\lg N$ 次比较。 代码 # var a = new[] { 1, 2, 5, 3, 5 }; Console.WriteLine(LocalMinimum(a)); static int LocalMinimum(int[] a) { var lo = 0; var hi = a.Length - 1; while (lo <= hi) { var mid = (hi - lo) / 2 + lo; var min = mid; // 取左中右最小值的下标 if (mid != hi && a[min] >= a[mid + 1]) min = mid + 1; if (mid ! ...
1.4.19 # 解答 # 问题类似于 POJ 上的一道题「滑雪」，从数值较高的一侧向周围数值较小的一侧移动，直到到达「山谷」（局部最小）。 首先在中间行搜索最小值，再将最小值与其上下两个元素比较，如果不满足题意，则“滑向”较小的一侧，矩阵被分为了两半（上下两侧）。 在较小的一侧，找到中间列的最小值，再将最小值与其左右两个元素比较，如果不满足题意，类似的移动到较小的一侧（左右两侧）。 现在查找范围缩小到了原来矩阵的四分之一，递归的进行上述操作，最后可以得到答案。 每次查找最小值都是对行/列进行遍历，遍历耗时和 N 成正比。 代码 # // 先查找 N/2 行中的最小元素，并令其与上下元素比较， // 如果不满足题意，则向相邻的最小元素靠近再次查找 var matrix = new[,] { { 26, 3, 4, 10, 11 }, { 5, 1, 6, 12, 13 }, { 7, 8, 9, 14, 15 }, { 16, 17, 18, 27, 20 }, { 21, 22, 23, 24, 25 } }; Console.WriteLine(MinimumRow(matrix, 0, 5, 0, 5)); static int MinimumRow(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength) { var min = int. ...
1.4.20 # 解答 # 首先给出 BitMax 类的官方 Java 实现：BitonicMax.java。 我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。 找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。 代码 # BitonicMax 类 # public class BitonicMax { /// <summary> /// 生成双调数组。 /// </summary> /// <param name="n">数组的大小。</param> /// <returns></returns> public static int[] Bitonic(int n) { var random = new Random(); var mid = random.Next(n); var a = new int[n]; for (var i = 1; i < mid; i++) { a[i] = a[i - 1] + 1 + random. ...
1.4.21 # 解答 # 直接将 Contains() 实现为二分查找即可。 代码 # /// <summary> /// 检查数组中是否存在指定元素。 /// </summary> /// <param name="key">要查找的值。</param> /// <returns>存在则返回 true，否则返回 false。</returns> public bool Contains(int key) { return Rank(key, 0, this.a.Length - 1) != -1; } /// <summary> /// 二分查找。 /// </summary> /// <param name="key">关键值。</param> /// <param name="lo">查找的起始下标。</param> /// <param name="hi">查找的结束下标。</param> /// <returns>返回关键值的下标，如果不存在则返回 -1。</returns> public int Rank(int key, int lo, int hi) { while (lo <= hi) { int mid = (hi - lo) / 2 + lo; if (key < this. ...
1.4.22 # 解答 # 普通二分查找是通过除法不断减半缩小搜索范围。 这里我们用斐波那契数列来缩小范围。 举个例子，例如数组大小是 100，比它大的最小斐波那契数是 144。 斐波那契数列如下：0 1 1 2 3 5 8 13 21 34 55 89 144 我们记 F(n) = 144,F(n-1) = 89, F(n-2) = 55。 我们先查看第 0 + F(n-2) 个数，如果比关键值小则直接将范围缩小到 [55, 100]；否则则在[0, 55]之间查找。 之后我们令 n = n-1。 递归上述过程即可完成查找。 代码 # /// <summary> /// 使用斐波那契数列进行的查找。 /// </summary> /// <param name="a">查找范围。</param> /// <param name="key">关键字。</param> /// <returns>返回查找到的关键值下标，没有结果则返回 -1。</returns> static int Rank(int[] a, int key) { // 使用斐波那契数列作为缩减范围的依据 var fk = 1; var fk1 = 1; var fk2 = 0; // 获得 Fk，Fk需要大于等于数组的大小，复杂度 lgN while (fk < a. ...