Codility Lesson 15題-MinAbsssSumOfTwo


質問:https://app.codility.com/programmers/lessons/15-caterpillar_method/min_abs_sum_of_two/start/
問題を簡単に説明すると、2つのパラメータの絶対値の差の中で最小の値を求めることになります.したがって,因子の絶対値を基準に並べ替えた方が効率的であると考えられる.ソート後,付着した因子間の絶対値の差は最小であり,付着した因子を比較するだけでよい.(0,0)のように同じindexのパラメータでpairを構成することもできるので、絶対値が最も小さい数字の2倍の値から最小値を探す.他の繰り返しパラメータからなるpairはこれより大きい必要があるので、チェックする必要はありません.
def solution(A):
    A.sort(key=lambda x: abs(x))  # 인자의 절대 값 기준으로 정렬

    minimum = abs(A[0] + A[0])  # 중복된 인자로 구성 된 pair는 가장 작은 인자로만 체크하면 된다
    
    for i in range(len(A) - 1):
    	# 정렬을 했기 때문에 서로 붙어있는 인자가 절대 값의 차이가 가장 작을 수 밖에 없다
        minimum = min(minimum, abs(A[i] + A[i + 1]))  
    
    return minimum
時間複雑度O(N*log(N))