如何優化我的代碼以運行大值也

下面是我的代碼。對於小值它返回我正確的答案我在這裏做的是找到任何兩個數字之間的最小差異，以便它不形成負面值。其實輸入線是每年的成本，我需要找到最小的損失（是的，它必須是一個損失）。當輸入很大時，說20000個數字，我得到一個超時錯誤。以下是測試用例的鏈接：https://hr-testcases-us-east-1.s3.amazonaws.com/27771/input12.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1502978445&Signature=vKwJ0MC3G1U3DXKE1N0qSruD5EI%3D&response-content-type=text%2Fplain 如何優化我的代碼以運行大值也

第一行包含數值，後續行包含值。

#!/bin/python 

import sys 

number = long(raw_input().strip()) 
cost=map(long,raw_input().strip().split()) 
flag=1 
j=0 
mincost=max(cost) 

print (mincost) 

while j < number: 
    k=j+1 
    while k<number: 
    if mincost>abs(cost[j] - cost[k]) and cost[j]> cost[k]: 
     mincost=abs(cost[j] - cost[k]) 
    k+=1 
    j+=1 

print mincost

來源

2017-08-17 leo jacob

究竟是什麼意思「不形成負數」？ – MSeifert

這意味着差異不應該小於0.真正的問題陳述涉及以下每個值作爲多年來房屋的成本。問題涉及最低成本，以便我以最小損失出售它（應該是虧損）。例如：測試案例：3 5 10 3這裏房子可以以5-3 = 2 PS的價格出售：前3個是超過它的價值數量。 –

對於20,000個數字，您有（20,000 x 19,999）/ 2 = 199,990,000兩兩比較。這是O（n^2）的複雜性。但是，如果對值進行排序，則兩個相鄰數字之間會出現最小差異。由於排序是O（n log n），因此可以通過（a）對值進行排序，然後（b）找出連續對之間的最小差異來改進算法。

costs = [5, 4, 1, 8, 12] 

sorted_costs = sorted(costs) 
pairs = zip(sorted_costs[:-1], sorted_costs[1:]) 
differences = map(lambda (a, b): b - a, pairs) 

print(min(differences)) # 1

唯一的問題是你是否可以在O（n）時間達到相同的結果。如果您的值是整數，則可以將排序減少到O（n）：

costs = [5, 4, 1, 8, 12] 

min_cost = min(costs) 
max_cost = max(costs) 

flag_list = [False] * (max_cost - min_cost + 1) 
for cost in costs: 
    flag_list[cost - min_cost] = True 

sorted_costs = [i + min_cost for i, b in enumerate(flag_list) if b]

來源

2017-08-17 14:00:00

爲什麼要導入sys？ '旗'的用法是什麼？如果你有足夠的RAM，我會做這樣的事情：

import numpy as np 
number = 20000 
cost = np.random.rand(number) * 1e6 # just for the example 
current_min = 1e10 # just for the example 
for i,j in enumerate(cost): 
    diff = j-cost[i+1:] 
    pos = diff > 0 
    if pos.any(): 
     temp = np.min(diff[pos]) 
     if temp<current_min: 
      current_min = temp 
print(final estimation: ',current_min)

來源

2017-08-17 14:37:15

如何優化我的代碼以運行大值也

回答

相關問題