題目：給定數(shù)組arr淤堵，找出數(shù)組中的最大值和最小值。其中顷扩，數(shù)組中的值兩兩各不相同拐邪。
分析：采用分治法。將數(shù)組兩兩一對(duì)分組隘截，如果數(shù)組元素個(gè)數(shù)為奇數(shù)個(gè)扎阶，就把最后一個(gè)元素單獨(dú)分為一組，偶數(shù)個(gè)則不用婶芭，然后分別對(duì)每一組中相鄰的兩個(gè)元素進(jìn)行比較东臀，把兩者中元素值較小的數(shù)放在數(shù)組的左邊，值大的數(shù)放在數(shù)組的右邊犀农，比較n/2此就能夠?qū)?shù)組分組完成惰赋。為此，最小值一定在每一組的左邊部分井赌，最大值一定在每一組的右邊部分谤逼，接著只需要在每一組的左邊部分查找最小值，右邊部分查找最大值仇穗，查找分別需要比較n/2-1次和n/2-1次筝野∧啵總共大約為n/2*3。
code:
def getMaxAndMin(arr):
? ? if arr is None:
? ? ? ? print("參數(shù)不合法")
? ? ? ? return
? ? # 兩兩分組痊夭，把較小的數(shù)放在數(shù)組的左半部分舞丛，把較大的數(shù)放在右半部分
? ? i = 0
? ? while i < (len(arr) - 1):
? ? ? ? if arr[i] > arr[i + 1]:
? ? ? ? ? ? temp = arr[i]
? ? ? ? ? ? arr[i] = arr[i + 1]
? ? ? ? ? ? arr[i + 1] = temp
? ? ? ? i += 2
? ? # 在各個(gè)分組的左半部分查找最小值
? ? minNum = arr[0]
? ? i = 2
? ? while i < len(arr):
? ? ? ? if arr[i] > minNum:
? ? ? ? ? ? minNum = arr[i]
? ? ? ? i += 2
? ? maxNum = arr[1]
? ? # 在各個(gè)分組的右半部分查找最大值
? ? i = 3
? ? while i < len(arr):
? ? ? ? if arr[i] > maxNum:
? ? ? ? ? ? maxNum = arr[i]
? ? ? ? i += 2
? ? # 如果數(shù)組中元素個(gè)數(shù)是奇數(shù)哥耘子，最后一個(gè)元素被分為一組果漾，需要與其比較再確定最大最小值。
? ? if len(arr) % 2 == 1:
? ? ? ? if maxNum < arr[len(arr) - 1]:
? ? ? ? ? ? maxNum = arr[len(arr) - 1]
? ? ? ? if minNum > arr[len(arr) -1]:
? ? ? ? ? ? minNum = arr[len(arr) -1]
? ? return maxNum, minNum
if __name__ == "__main__":
? ? arr = [7, 3, 19, 40, 4, 7, 1]
? ? print(getMaxAndMin(arr))
程序的運(yùn)行結(jié)果為：40谷誓， 1
