我在面试中遇到了这样一个问题:
一个地区有工厂生产污染性气体,每个工厂都要安装过滤器以减少污染.安装的每个过滤器将使那家工厂的污染减少一半.每个工厂可以有多个过滤器.有一个N个整数的列表,代表该地区N家工厂的污染水平.找出减少一半总污染所需的最小过滤器数量.
例如,[3,5,6,1,18]是5家工厂的污染水平列表
总体污染=3+5+6+1+18=33(目标为33/2=16.5)
在索引=4的工厂安装过滤器-->;污染水平将为[3,5,6,1,9]
在索引=4的工厂安装过滤器-->;污染水平将为[3,5,6,1,4.5]
在索引=2的工厂安装过滤器-->;污染水平将为[3,5,3,1,4.5]
至少需要3个过滤器,达到总污染的一半.
N是[1…30000]范围内的整数.列表中的每个元素都是[0…70000]范围内的整数
我想出的解决方案很简单:
def solution(A):
total = sum(A)
target = total/2
count = 0
while total>target:
count+=1
max_p = max(A)
total-= max_p/2
A.remove(max_p)
A.append(max_p/2)
return count
除了时间复杂度似乎为O(N^2)之外,这一方法效果良好.有人能提出一种时间复杂度较低(最好是O(N))的解决方法吗?