采购两个类型的零件A和B

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

刷题网 一千零二十九

只是想了一下，没测试。

首先对于k个公司中每个公司的tuple比如(1, 10)指定一个id. 这一步应该是需要编成list或者map/dict.
1+1的case：维护两个list a[2]和b[2]，length都是2，分别指产品A和B的最低报价id和次最低报价id. 然后遍历一次所有公司，拿到A和B的最低价格的公司id和次最低的公司id. 这个过程是 O(k). 然后尝试(a[0], b[0]), (a[1], b[0]), (a[0], b[1])哪个和最小，遇到同一个公司id则忽略。
m+n的case：维护两个min-heap，各自capacity是m+n. 分别存储A和B的前(m+n)个最低报价的公司id. 模仿k-th largest number，遍历所有k个公司，拿到两个产品的最低的(m+n)个报价，这个过程是 O(k + log(m + n))。然后从两个堆中小一点的堆顶开始merge两个堆（删堆顶元素），遇到已经出现的公司id则忽略。每一次删元素是 O(log(m + n))，一直到分别选出m和n个产品。这个过程最坏情况是 O((m + n) * log(m + n))，最好情况是 O(max(m, n) * log(m + n)).

补充内容 (2019-5-1 23:33):
m+n的case的遍历过程是O(k * log(m + n))

补充内容 (2019-5-1 23:45):
merge两个堆的过程我想的是类似于merge sort后期合并的过程

按照之前的想法写了一个1+1的：

1. def case_one_plus_one(company_list):
   
2.     if len(company_list) < 2:
   
3.         return []
   
4. 
   
5.     a = [0, 1] if company_list[0][0] < company_list[1][0] else [1, 0]
   
6.     b = [0, 1] if company_list[0][1] < company_list[1][1] else [1, 0]
   
7.     for index, c in enumerate(company_list):
   
8.         if c[0] <= company_list[a[0]][0]:
   
9.             a[0] = index
   
10.         elif c[0] <= company_list[a[1]][0]:
    
11.             a[1] = index
    
12.         if c[1] <= company_list[b[0]][1]:
    
13.             b[0] = index
    
14.         elif c[1] <= company_list[b[1]][1]:
    
15.             b[1] = index
    
16. 
    
17.     print(a)
    
18.     print(b)
    
19.     if a[0] != b[0]:
    
20.         return company_list[a[0]][0] + company_list[b[0]][1]
    
21.     else:
    
22.         return min(company_list[a[0]][0] + company_list[b[1]][1], company_list[a[1]][0] + company_list[b[0]][1])
    
23. 
    
24. if __name__ == '__main__':
    
25.     company_list = [(7, 80), (24, 89), (101, 95), (168, 101)]
    
26.     case_one_plus_one(company_list)
    

复制代码

补充内容 (2019-5-2 11:18):
len < 2 应该是return 0

lalxyy 发表于 2019-5-1 23:33
只是想了一下，没测试。

首先对于k个公司中每个公司的tuple比如(1, 10)指定一个id. 这一步应该是需要编 ...

然后从两个堆中小一点的堆顶开始merge两个堆（删堆顶元素）
能再詳細解釋一下嗎？沒太想明白

TTTWangTingting 发表于 2019-5-22 07:04
然后从两个堆中小一点的堆顶开始merge两个堆（删堆顶元素）
能再詳細解釋一下嗎？沒太想明白

我记得刷题网有merge两个array的原型。忘了题目叫什么。可以参考这个操作。