2017-12-31 62 views
0

私は来週、最初のラウンドのインタビューでコーディングの挑戦をします。人事部は、コーディングの難題プラットフォームとしてCodilityを使用すると述べた。私はCodi​​lity Lessonsを使って練習しています。Pythonを使ったコーディングでのPassingCars

私の問題は、正確度で非常に高い得点を得ることが多いのですが、時間の複雑さを測るパフォーマンススコアは恐ろしいです(私はしばしば0%を得ます)。

はここで質問です: https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

私のコードは次のようになります。これは、O(N)であると考えられる

def solution(A): 
    N = len(A) 
    my_list = [] 
    count = 0 
    for i in range(N): 
     if A[i] == 1: 
      continue 
     else: 
      my_list = A[i + 1:] 
      count = count + sum(my_list) 
    print(count) 
    return count 

が、鉱山がOである(N ** 2)。

  1. 誰かがO(N)時間の複雑さの下でこの問題を解決するにはどうすればよいですか?

  2. 一般的に、アルゴリズムに関する質問を見ると、どのようにアプローチを思いついていますか?

答えて

4

ゼロが見つかるたびに、配列全体を合計しないでください。それはそれをO(n^2)にします。代わりに、見つかったすべてのゼロは、次のそれぞれについて+1を与えることに注意してください。

def solution(A): 
    zeros = 0 
    passing = 0 
    for i in A: 
     if i == 0: 
      zeros += 1 
     else: 
      passing += zeros 
    return passing 
+0

ありがとうございました!このような素晴らしい解決策は、どのように思いつきますか?私はそれに100時間を費やしても、私が解決策を考え出すことはできないと思う。それは練習によるのでしょうか? –

+0

多くの実践。しかし、O(n)が必要な場合は、各要素を1回だけ調べる必要があります。あなたは常に良いスタートである実用的なソリューションを持っていました。しかし、作業中のソリューションを見て、各要素を何度も見る必要がないかもしれない方法を見てください。 –

+0

私は参照してください。ありがとうございました。 –

関連する問題