題目：對(duì)于一個(gè)由N個(gè)整數(shù)組成的數(shù)組兄世，需要比較多少次才能找出最大值和最小值的數(shù).
常規(guī)解法
時(shí)間復(fù)雜度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>
解法二
由于最大的數(shù)和最小的數(shù)不會(huì)是同一個(gè)數(shù)(N!=1)啼辣，可以把數(shù)組分成兩部分，然后再從這兩部分中分別找出最大的數(shù)和最小的數(shù)碘饼。首先按順序?qū)?shù)組中相鄰的兩個(gè)數(shù)分在同一組熙兔，接著比較同一組中奇數(shù)位數(shù)字和偶數(shù)位字，將較大的房子偶數(shù)位上艾恼，較小的數(shù)放在奇數(shù)位上住涉，經(jīng)過N/2次比較的預(yù)處理后，較大的數(shù)都放到了偶數(shù)位置上钠绍，較小的數(shù)則放到了奇數(shù)位置上舆声，最后從奇偶數(shù)位上分別求出Max和min,各需要比較N/2次。整個(gè)算法共需要比較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>
解法三
解法二需要改變?cè)袛?shù)組中數(shù)據(jù)的位置媳握，其實(shí)可以不比較其中的數(shù)字:
<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>
測(cè)試代碼:
<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-最大最小的數(shù)值---(findResult1)---最小數(shù)組--(findResult2)---(findResult3)")`</code></pre>
