题目：对于一个由N个整数组成的数组，需要比较多少次才能找出最大值和最小值的数.
常规解法
时间复杂度O(2N)
<pre><code>` func minMax(arr:[Int])->(Int,Int) {
var min:Int = arr[0]
var max:Int = arr[0]
for i in 0..<arr.count {
if arr[i] < min {
min = arr[i]
}
if arr[i] > max {
max = arr[i]
}
}
return (min,max)
}`</code></pre>
解法二
由于最大的数和最小的数不会是同一个数(N!=1)，可以把数组分成两部分，然后再从这两部分中分别找出最大的数和最小的数。首先按顺序将数组中相邻的两个数分在同一组，接着比较同一组中奇数位数字和偶数位字，将较大的房子偶数位上，较小的数放在奇数位上，经过N/2次比较的预处理后，较大的数都放到了偶数位置上，较小的数则放到了奇数位置上，最后从奇偶数位上分别求出Max和min,各需要比较N/2次。整个算法共需要比较1.5*N次。
<pre><code>` func minMax1(arr:[Int]) -> (Int,Int) {
var data:[Int] = arr
var min:Int = data[0]
var max:Int = data[0]
for i in stride(from: 0, to: data.count - 1, by: 2) {
if data[i] < data[i + 1]{
swap(&data[i], &data[i+1])
}
}
for i in stride(from: 0, to: data.count - 1, by: 2) {
if data[i] > max {
max = data[i]
}
if data[i+1] < min {
min = data[i+1]
}
}
if data[data.count-1] > max {
max = data[data.count - 1]
}
if data[data.count-1] < min {
min = data[data.count - 1]
}
return (min,max)
}`</code></pre>
解法三
解法二需要改变原有数组中数据的位置，其实可以不比较其中的数字:
<pre><code>` func minMax2(arr:[Int]) -> (Int,Int) {
var data:[Int] = arr
var min:Int = data[0]
var max:Int = data[0]
for i in stride(from: 0, to: data.count - 1, by: 2) {
let tempMax:Int = data[i] > data[i+1] ? data[i] : data[i+1]
let tempMin:Int = data[i] < data[i+1] ? data[i] : data[i+1]
if tempMax > max {
max = tempMax
}
if tempMin < min {
min = tempMin
}
}
if data[data.count-1] > max {
max = data[data.count - 1]
}
if data[data.count-1] < min {
min = data[data.count - 1]
}
return (min,max)
}`</code></pre>
测试代码:
<pre><code>`var findArr:[Int] = [100,5,6,8,3,7,9,10,0,40,1,2]
var findResult1 = find.minMax(arr: findArr)
var findResult2 = find.minMax1(arr: findArr)
var findResult3 = find.minMax2(arr: findArr)
print("FlyElephant-最大最小的数值---(findResult1)---最小数组--(findResult2)---(findResult3)")`</code></pre>
