python取绝对值数组_Python算法——求数组中绝对值最⼩的
数
要求:
对于升序排列数组,数组中有正数、负数、或0,求数组中元素的绝对值最⼩的数。例如数组[-10,-5,-2,7,15,50]中绝对值最⼩的数为-2。
分析:
⽅法⼀:顺序⽐较法
最简单的⽅法就是从头到尾遍历数组元素,对每个数字求绝对值,然后⽐较就可以求出绝对值最⼩的数。
⽅法⼆:⼆分法
求绝对值最⼩的数分为三种情况:(1)如果数组中第⼀个元素为⾮负数,那么绝对值最⼩的数肯定为数组第⼀个元素;(2)如果数组最后⼀个元素的值为负数,那么绝对值最⼩的数肯定是数组最后⼀个元素;(3)如果数组中既有正数⼜有负数,⾸先到正负数分界点,如果分界点恰好为0,那么0就是绝对值最⼩的数。
否则通过⽐较分界点左右的正数与负数绝对值来确定最⼩的数。那么如何到正负数分界点呢?当然是⼆分法啦~~~
实现代码:
#⽅法⼀
# -*- 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
python获取数组长度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小时内删除。
发表评论