|
找出包含n个元素的数组中的最小值和最大值最简单的方法就是独立的使用n次循环然后分别得到最小值和最大值如是这样的共用了n次比较 但是我们可以使用比较次数更低的方法来找出最小值和最大值方法如下 先将一对元素互相进行比较然后把最小值跟当前最小值进行比较把最大值跟当前最大值进行比较因此每两个元素需要次比较 如果n 为奇数那么比较的次数是<![if supportFields]> <![endif]>次比较如果n 为偶数那么比较的次数是n/次比较因此不管是n是奇数还是偶数比较的次数至多是 具体的c# 代码如下 public void LookMinMaxElement(Int[] aref Int minref Int max) { for (int i = ; i <= aLength ; i+=) { if (!(i + >= aLength)) { if (a[i] < a[i + ]) { if (a[i] < min) { min = a[i]; } if (a[i + ] > max) { max = a[i + ]; } } else { if (a[i + ] < min) { min = a[i + ]; } if (a[i] > max) { max = a[i]; } } } } } 测试代码如下 [TestMethod()] public void LookMinMaxElementTest() { MinMaxElement target = new MinMaxElement(); // TODO: Initialize to an appropriate value int[] a = new Int[] { }; Int min = IntMaxValue; Int max = IntMinValue; targetLookMinMaxElement(a ref min ref max); AssertAreEqual( min); AssertAreEqual( max); a = new Int[] { }; min = IntMaxValue; max = IntMinValue; targetLookMinMaxElement(a ref min ref max); AssertAreEqual( min); AssertAreEqual( max); } |
