谷歌CodeJam過去的練習 - 減少運行時間

-4

我一直在從過去的谷歌Codejam算法從2010年，但時間複雜性是可怕的。谷歌CodeJam過去的練習 - 減少運行時間

下面是來自谷歌Codejam問題：https://code.google.com/codejam/contest/619102/dashboard

TLDR - 想象一下，兩個塔樓有跑起來的邊數軸，我們得出從一個建築物號線（比如10）線到另一點上其他建築物號碼行（從1開始）。如果我們這樣做n次，那些線會相交多少次？

我想知道如果有人在這裏能夠提出一種方法，我可以加快我的算法？ 4個小時後，我真的看不到一個，我失去了我的夢想。

這是我現在的代碼。

一個例子的輸入將是：

2 - （案件編號）

3 -

（在情況＃1線的數量）

案例1：2 - （1,10,5,5行之間的2個交點7,7）

2 - （電線的情況下，在＃2）

情況＃號2：0 - （無線相交）

def solve(wire_ints, test_case): 
    answer_integer = 0 
    for iterI in range(number_wires): 
     for iterJ in range(iterI): 
      holder = [wire_ints[iterI], wire_ints[iterJ]] 
      holder.sort() 
      if holder[0][1] > holder[1][1]: 
       answer_integer = answer_integer + 1 
    return("Case #" + str(test_case) + ":" + " " + str(answer_integer)) 

for test_case in range(1, int(input()) + 1): 
    number_wires = int(input()) 
    wire_ints = [] 
    for count1 in range(number_wires): 
    left_port,right_port = map(int, input().split()) 
    wire_ints.append((left_port,right_port)) 
    answer_string = solve(wire_ints, test_case) 
    print(answer_string)

這個算法對我給它的任何輸入都起作用，但正如我所說的那樣，它非常醜陋而且很慢。

幫助，將不勝感激！

來源

2016-09-03 jaa1234

我想你會在[codereview.se] – Rakete1111

得到更好的答案我會在那裏發佈兩個謝謝 – jaa1234

這也可能是題外話我想 – Rakete1111

由於N是1000，因此可以接受O(N^2)的算法。所以你必須做的是通過他們的一個終點對電線進行分類。

//sorted by first number 
1 10  
5 5 
7 7

然後你從一開始就處理每一行，並檢查它是否與之前的行有交集。如果它之前的一條線的第二個端點大於當前線的第二個點，則它們有交集。這需要兩個循環，因此O(N^2)的複雜性足以滿足N=1000。
您也可以將其解釋爲倒置計數。您必須計算列表按第一個結束點排序的第二個端點的反轉次數。

10 5 7 ->‌ number of inversions is 2, because of (10,5) and (10,7)

也有O(NlogN) approach來算，你不需要爲這個問題逆轉的次數。

來源

2016-09-03 14:17:58 Tempux

谷歌CodeJam過去的練習 - 減少運行時間

回答

相關問題