每周一课：L15 Caterpillar method(15.4
2019-02-20 本文已影响2人
AiFany
0.png
P15.4 MinAbsSumOfTwo
Find the minimal absolute value of a sum of two elements.
-
P15.4 两数和绝对值
计算所有两数和绝对值中最小的
设A为由N个整数组成的非空数组。一对索引(P, Q)的两数和绝对值|A[P] + A[Q]|，其中0 ≤ P ≤ Q < N。
例如，数组A：A[0] = 1，A[1] = 4，A[2] = -3。有6对索引（0，0），（0，1），（0，2），（1，1），（1，2），（2，2）：
- 索引（0，0）的两数和绝对值为|A[0]+A[0]|=|1+1|=2；
- 索引（0，1）的两数和绝对值为|A[0]+A[1]|=|1+4|=5；
- 索引（0，2）的两数和绝对值为|A[0]+A[2]|=|1+（−3）|=2；
- 索引（1，1）的两数和绝对值为|A[1]+A[1]|=|4+4|=8；
- 索引（1，2）的两数和绝对值为|A[1]+A[2]|=|4+（−3）|=1；
- 索引（2，2）的两数和绝对值为|A[2]+A[2]|=|（−3）+（−3）|=6；
编写函数：
def solution(A, N)
给定一个由N个整数组成的非空数组A，则返回该数组中任意索引的最小的两数和绝对值。
例如，针对上面的例子，函数应该返回1。针对数组A：A[0] = -8，A[1] = 4，A[2] = 5，A[3] =-10，A[4] = 3，函数应返回|（−8）+5|=3。
假定：
- N是区间[1，1,000,00]内的整数；
- 数组A的每个元素都是区间[-1,000,000,000，1,000,000,000]内的整数；
- 解题思路
首先把数组变为升序的。对于两个索引a,b，a<b。如果a的绝对值大于b值，说明a位置的元素肯定为负数，因此要使得和值最小，就要增大a。如果a的绝对值不大于b值，说明b位置的值肯定为正数，要使得和值变小，因此要减小b。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 15：Caterpillar method
# P 15.4 MinAbsSumOfTwo
def solution_worse(A):
"""
返回所有两数和的绝对值的最小值，时间复杂度O(N * N)
:param A: 数组A
return: 两数和绝对值的最小值
"""
length = len(A)
if length == 1:
return 2 * abs(A[0])
A.sort()
if A[-1] <= 0:
return min(abs(A[-1] + A[-1]), abs(A[-1] + A[-2]))
elif A[0] >= 0:
return min(abs(A[0] + A[0]), abs(A[0] + A[1]))
else:
min_num = []
for i in range(len(A)):
sum_num = abs(A[i] + A[i])
for j in range(i+1, len(A)):
if abs(A[i] + A[j]) > sum_num:
break
else:
sum_num = abs(A[i] + A[j])
min_num.append(sum_num)
return min(min_num)
def solution(A):
"""
返回所有两数和的绝对值的最小值，时间复杂度O(N * log(N))
:param A: 数组A
return: 两数和绝对值的最小值
"""
A.sort()
f_pos = 0
s_pos = len(A) - 1
min_num = 2*10**9
while f_pos <= s_pos:
min_num = min(min_num, abs(A[f_pos]+A[s_pos]))
if abs(A[f_pos]) > abs(A[s_pos]): # 说明f_pos位置一定为负数，此时需要增大负数的值使得和值绝对值变小，因此前一个索引加1
f_pos += 1
else: # f_pos位置的数为一个较小的负数或者正数，因此要减小后面正数的数值，为了获取较小的和值
s_pos -= 1
if min_num == 0: # 因为两数和绝对值最小为0，提前退出
return 0
return min_num
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
