Codibility-使用Python进行磁带平衡训练

您可以将代码更改为下面这样的代码,以增加复杂性 O(N) .

def solution(A):          
    s = sum(A)
    m = float('inf')
    left_sum = 0
    for i in A[:-1]:
        left_sum += i
        m = min(abs(s - 2*left_sum), m)
    return m

正如@darkvalance所写的功能性方法,但有评论:

from itertools import accumulate

def solution(A):
    array_sum = sum(A)  # saving sum of all elements to have an O(n) complexity

    # accumulate returns accumulated sums
    # e.g. for input: [3, 1, 2, 4] it returns: [3, 4, 6, 10]
    # we are passing a copy of the array without the last element
    # including the last element doesn't make sense, becuase
    # accumulate[A][-1] == array_sum
    accumulated_list = accumulate(A[:-1])

    return min([abs(2*x - array_sum) for x in accumulated_list])

回答你的问题-是O(n*n),因为 sum() 函数是O(n)时间复杂度,您在 for 循环使用 N 元素,也就是O(N)。

因此,算法的时间复杂度将为O(N*N)

我的java代码 O(N)

class Solution {
public int solution(int[] arr) {

   int sum = 0;

   for(int i = 0; i<arr.length; i++){
       sum = sum + arr[i];
   }



  int  minSum = 100000;
  int  tempSum = 0;
  int previousSum = 0;
   for(int i = 0; i<arr.length-1; i++){

       previousSum = previousSum + arr[i];

      tempSum = Math.abs(previousSum - (sum - previousSum));

      if(minSum > tempSum){
          minSum = tempSum;
      }


   }

   return minSum;
}

}

我的python代码O(N)

def solution(A):
    # write your code in Python 3.6
    mini = float('inf')
    check = A[0]
    total = sum(A)-check
    for i in range(1, len(A)):
        diff = abs(check-total)
        total -= A[i]
        check += A[i]
        if diff < mini:
            mini = diff
    return mini

功能进近O(N)。累计提供列表的累计运行和。我们可以用列表的和以及每个点的累积和来计算两个数组之间的差。

from itertools import accumulate

def solution(A):
    s = sum(A)
    l = list(accumulate(A[:-1]))
    return min([abs(2*x - s) for x in l])

def solution(A):
   res = []
   left_sum = 0
   right_sum = sum(A)
   for i in range(0, len(A)-1):
       left_sum += A[i]
       right_sum = right_sum - A[i]
       res.append(abs(right_sum-left_sum))
   return min(res)

目前,您正在中反复计算总和 first_tape 和 second_tape . 您需要做的是存储总和,并使用差分计算总和。例如,如果您的阵列 [1,2,3,4] ,总金额为 10 . 让我们假设 第一个\u磁带 大小相同 1 或者换言之 第一个\u磁带 是 [1] 所以第一盘磁带的总和是 1. . 那么剩下的第二个磁带的总和将是

`total sum - first_tape sum`

区别在于

first_tape sum - (total sum - first_tape sum)

可以通过执行以下操作来计算同一循环中的第一个\u磁带和:

previous sum += i (where i is the current array element)

所以解决方案是 N .

这里我还添加了一个检查,以确定数组的元素何时为0

def MinimialDiff(A):

    if len(A) == 2:
        return abs(A[0]-A[1])

    tot_sum = sum(A)
    min_value = float('inf')
    left_sum = 0
    for x in range(0,len(A)-1):
        if A[x] == 0:
            continue
        left_sum += A[x]
        temp = abs(2*left_sum-tot_sum)
        min_value = min(min_value,temp)

    return min_value

这是我对磁带平衡问题的原始解决方案

def solution(A) :

    import numpy as np

    # Check if the supplied array is empty or single element
    if len( A ) < 2 :
        return -1

    # Otherwise, create two NumPy Arrays of (non-linear) accumulated sums:

    # All but last, Start to End
    Array_Sum_Accumulated  = np.array( list( np.cumsum( A[  0 : -1 :  1 ] ) )[ : :  1 ] )

    # All but first, End to Start
    Array_Sum_Acc_Reversed = np.array( list( np.cumsum( A[ -1 :  0 : -1 ] ) )[ : : -1 ] )

    # Array of Absolute Diffenences using fast (precompiled) and simple NumPy magic
    Array_Sum_Difference = abs( Array_Sum_Accumulated - Array_Sum_Acc_Reversed )

    # for debugging only
    if len( A ) <= 20 :
        print( "%s\n%s\n%s" % ( Array_Sum_Accumulated, Array_Sum_Acc_Reversed, Array_Sum_Difference ) )

    return min( Array_Sum_Difference )

不幸的是,Codibility不允许为本课程导入NumPy模块。因此,这就是导入IterTools模块而不是NumPy的解决方案,它(最终)产生了全面的100%结果:

def solution(A):

    from itertools import accumulate

    # Check if the supplied array is empty or single element
    if len( A ) < 2 :               
        return -1

    # If only two elements return the Absolute Difference of them
    if len( A ) == 2 :
        return abs( A[ 0 ] - A[ 1 ])

    # Otherwise, create two lists of (non-linear) accumulated sums:

    # All but last, Start to End
    Array_Sum_Accumulated  = list( accumulate( A[  0 : -1 :  1 ] ) )[ : :  1 ]

    # All but first, End to Start
    Array_Sum_Acc_Reversed = list( accumulate( A[ -1 :  0 : -1 ] ) )[ : : -1 ]

    # List of Absolute Differences using the slower (interpreted) loop
    Array_Sum_Difference = [ ]
    for i in range( 0, len( Array_Sum_Accumulated ) ) :
        Array_Sum_Difference.append( abs( Array_Sum_Accumulated[ i ] - Array_Sum_Acc_Reversed [ i ] ) )

    # For debugging only
    if len( A ) <= 20 :
        print( "%s\n%s\n%s" % ( Array_Sum_Accumulated, Array_Sum_Acc_Reversed, Array_Sum_Difference ) )

    return min( Array_Sum_Difference )

多亏了darkvalance的IterTools解决方案,以及坚韧的Raptor(非常有启发性的)对所用逻辑的澄清。

还要感谢Jun Jang尝试了两条分割带的解决方案,该解决方案表明非线性累积可以提供多条“带对”,因为相同的最小绝对差值可以出现在“带”上的多个平衡点上。

darkvalance提供的IterTools解决方案不仅提供了完全相同的结果,而且看起来非常像Pythonic,在97%以上的测试中(在对100000个元素的阵列进行了100000次测试之后),它的性能超过了Three NumPy Arrays解决方案。

祝贺我希望有一天我的代码会像你的一样。

此代码段也是一种可能的解决方案

def solution(A):
    # write your code in Python 3.6
    d=[]
    for i in range(1,len(A)):
        d.append(abs(sum(A[:i])-sum(A[i:])))
    return list(set(d))[0]