Python算法——求数组中绝对值最⼩的数
要求：
对于升序排列数组，数组中有正数、负数、或0，求数组中元素的绝对值最⼩的数。例如数组[-10,-5,-2,7,15,50]中绝对值最⼩的数为-2。
分析：
⽅法⼀：顺序⽐较法
最简单的⽅法就是从头到尾遍历数组元素，对每个数字求绝对值，然后⽐较就可以求出绝对值最⼩的数。
⽅法⼆：⼆分法
求绝对值最⼩的数分为三种情况：(1)如果数组中第⼀个元素为⾮负数，那么绝对值最⼩的数肯定为数组第⼀个元素；(2）如果数组最后⼀个元素的值为负数，那么绝对值最⼩的数肯定是数组最后⼀个元素；(3)如果数组中既有正数⼜有负数，⾸先到正负数分界点，如果分界点恰好为0，那么0就是绝对值最⼩的数。否则通过⽐较分界点左右的正数与负数绝对值来确定最⼩的数。那么如何到正负数分界点呢？当然是⼆分法啦~~~
实现代码：
#⽅法⼀
python获取数组长度# -*- coding:utf-8 -*-
def findMin(array):
if array == None or len(array) <= 0:
print("输⼊参数不合理")
return 0
mins = 2**32
i = 0
while i < len(array):
if abs(array[i]) < abs(mins):
mins = array[i]
i += 1
return mins
if __name__ == "__main__":
arr = [-10,-5,-2,7,15,50]
print("绝对值最⼩的数为："+str(findMin(arr)))
运⾏结果
绝对值最⼩的数为：-2
#⽅法⼆
def findMin(array):
if array == None or len(array) <= 0:
print("输⼊参数不合理！")
return 0
lens = len(array)
#数组中没有负数
if array[0] >= 0:
return array[0]
#数组中没有正数
if array[lens-1] <= 0:
return array[lens-1]
mid = 0
begin = 0
end = lens-1
absMin = 0
#数组中既有正数也有负数
while True:
mid = int(begin + (end-begin)/2)
#如果等于0，那么就是绝对值最⼩的数
if array[mid] == 0:
return 0
elif array[mid] > 0: #如果⼤于0，正负数分界点在左侧，继续左半部分查            if array[mid-1] > 0:
end = mid - 1
elif array[mid-1] == 0:
return 0
else:  #到正负数分界点
break
else: #如果⼩于0，在数组右半部分查
if array[mid+1] < 0:
begin = mid + 1
elif array[mid + 1] == 0:
return 0
else:  #到正负数分界点
break
#获取正负数分界点处绝对值最⼩值
if (array[mid] > 0): #说明array[mid-1]为负数，array[mid]为正数
if array[mid] < abs(array[mid-1]):
absMin = array[mid]
else:
absMin = array[mid-1]
else:  #说明array[mid]为负数，array[mid+1]为正数
if abs(array[mid]) < array[mid+1]:
absMin = array[mid]
else:
absMin = array[mid+1]
return absMin
if __name__ == "__main__":
arr = [-10,-5,-2,7,15,50]
print("绝对值最⼩的数为："+str(findMin(arr)))
运⾏结果
绝对值最⼩的数为：-2
性能分析：
⽅法⼀平均时间复杂度为O(N)，空间复杂度为O(1)。
⽅法⼆采取了⼆分查，算法平均时间复杂度为O(log)，其中N为数组长度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。