計算數組中的最大值與最小值

首先，從題目可以看出，對于大部分的開發者來說，這是一個基礎得不能再基礎的題目了，是以，知道如何求解以及對求解過程完全掌握的話，可以不用往下看了，如果對于這個問題希望能複習一下，或者不太了解的話，可以接着往下看。我寫的實在也有浪費閱讀者時間的嫌疑，而目的也隻是希望用清晰明确的語言将這些簡單的題目講解清楚，來提升表達方面的能力。

題目描述

給定一個無序的數組，求出這個數組中的最大值與最小值。

解題思路

比方說，有一個無序的數組[3,5,7,2],可以看出，這個數組中最大值是2，最小值是7。

如何求呢？ 先求最大值，我們可以先聲明一個變量為最大值，這個變量初始值為數組中的第一個元素，然後循環周遊這個數組，将目前這個最大值與目前周遊的元素進行比較，如果目前的元素比這個變量大，則更新這個最大值為目前元素的值。

代碼實作

使用swift代碼，注意此時代碼中元素的類型應該使用泛型，傳回類型應該為optional(可選型),因為數組如果為空的話，并不存在最大值與最小值。如下代碼為求數組中的最大值。

func findMax<T:Comparable>(_ array: [T]) ->T? {
    guard var max = array.first else { return nil }
    
    for element in array.dropFirst() {
        if(element > max){
            max = element
        }
    }
    return max
}
複制代碼
           

以[3,5,7,2]這個數組為例，進行具體的講解，首先，假設數組中的第一位3為最大值，先與後面的5開始比較，5比較大，此時更新5為最大值，再與後面的7比較，7又比5大，更新7位最大值，7在與2進行比較，7比2大，保持不變，循環結束，7為數組中的最大值。

求最小值同樣思路：

func findMin<T:Comparable>(_ array: [T]) ->T? {
    guard var min = array.first else { return nil }
    
    for element in array.dropFirst() {
        if(element < min){
            min = element
        }
    }
    return min;
}
複制代碼
           

另外，在語言的标準庫中，也可能封裝好了求解最大值，最小值的函數，可以直接使用。

let array = [4,12,56,32,65,2,3,6]
array.min() // 求最小值 傳回2
array.max() // 求最大值 傳回65
複制代碼
           

如何把求最大值與最小值封裝到一個函數裡呢？在swift中，可以使用元組同時傳回最大值與最小值。

示例代碼：

func findMaxMin<T:Comparable>(_ array:[T]) ->(min: T,max:T)? {
    guard var min = array.first else { return nil }
    
    var max = min
    
    let start = array.count % 2 // 如果個數為單數，則從index = 1開始周遊
    for i in stride(from: start, to: array.count, by: 2) {
        let pair = (array[i],array[i+1])
        
        if(pair.0 > pair.1){
            if pair.0 > max {
                max = pair.0
            }
            
            if pair.1 < min {
                min = pair.1
            }
            
        } else {
            if pair.1 > max {
                max = pair.1
            }
            
            if pair.0 < min {
                min = pair.0
            }
        }
    }
    
    return (min, max)
}
複制代碼
           

代碼的整體邏輯并不難了解，以數組[3,7,2,5,9] 為例進行講解。

首先取首元素作為最大值與最小值，然後判斷數組元素的個數是單數還是雙數，如果是單數，則周遊數組從index = 1開始，這是因為數組進行周遊時，是成對進行周遊。

數組[3,7,2,5,9]元素個數是單數，第一次取7，2組成元組(7,2)，然後7 與2 進行比較，7比2大，是以7與設定為最大值的首元素進行比較，7比3大，7取代3成為最大值。然後2與同樣設定為最小值的3進行比較，2比3小，2取代3成為最小值。

繼續下一組5，9組成元組，先組内進行比較，9比5大，是以用9與暫時的最大值7進行比較，9比7大，9取代7成為最大值。然後用5與暫時的最小值2進行比較，2比5小，2依舊保持為目前的最小值。

循環結束，目前的最小值2，最大值9，組成元組(2, 9),作為函數的傳回值進行輸出。自此，函數運作結束。

在有些語言中或許沒有類似元組的資料結構，也可以使用數組，數組的第一個元素存儲最小值，第二個元素存儲最大值。也可以使用map,進行鍵值存儲後作為函數傳回值輸出。

時間複雜度分析

循環周遊了數組一遍，并取出元素的每個元素進行了最大或最小的比較，是以這個算法的時間複雜度是O(n)。

轉載于:https://juejin.im/post/5d3a76f05188257f3850e067