亚麻欧唉

周六做了亚麻的欧哎，第一题测试用力全国，第二题13/15。跪！

第一题，找距离最近的k个点，优先队列做做。

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

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

1. from random import randint
   
2. 
   
3. from bisect import bisect_left
   
4. def findtarget(listA, listB, target):
   
5.     # brute force (upper boundary): try each combination: m * n and find the result
   
6.     # sortA, sortB: mlogm + nlogn, binary search num from A in B. mlogn
   
7.     # total: mlogm + nlogn + mlogn
   
8.     listA.sort()
   
9.     listB.sort()
   
10.     # distance
    
11.     res = [float('inf'), None, None]
    
12.     smallest, biggest = listB[0], listB[-1]
    
13.     for val in listA:
    
14.         # currVal + biggest number in B not able to bigger than target, the maxSum = currVal + biggest
    
15.         if val + biggest < target:
    
16.             curr = val + biggest
    
17.             if target - curr < res[0]:
    
18.                 res = [target - curr, val, biggest]
    
19.             continue
    
20. 
    
21.         # currVal + smallest number in B exceed target: we shall stop here
    
22.         if val + smallest > target:
    
23.             break
    
24. 
    
25.         # currVal + biggest > target and currVal + smallest < target
    
26.         index = bisect_left(listB, target - val)
    
27.         print index, val, listA, listB
    
28.         if target - val == listB[index]:
    
29.             return [val, listB[index]]
    
30.         else:
    
31.             curr = val + listB[index - 1]
    
32.             if target - curr < res[0]:
    
33.                 res = [target - curr, val, listB[index - 1]]
    
34.     return res[1:]
    
35. 
    
36. A = [randint(0, 100) for _ in xrange(10)]
    
37. B = [randint(0, 100) for _ in xrange(10)]
    
38. print A, B
    
39. print findtarget(A, B, 100)
    
40. 
    

复制代码

GabrielaSong 发表于 2018-12-17 23:48
请问楼主明白知道是错了那两个test case吗？数组里面的数和target有范围吗? 可以是负数吗? test case会不会 ...

两个数组里面可能会有重复数字，要求返回值是【A里面的index，B里面的index】。并不是直接要A和B里面的值。我自己的解法没有handle两个数组里面都有重复的情况，所以有两个case没过。过了的case应该是两个数组里面没有重复值，或者只有一个数组里面有重复值。

zenki 发表于 2018-12-18 00:45
两个数组里面可能会有重复数字，要求返回值是【A里面的index，B里面的index】。并不是直接要A和B里面的值 ...

多谢楼主！楼主说的handle两个数组里都有重复的情况的意思是，可能有多个最优解要把所有最优解都返回是吗？

第二题是sortA, sortB: mlogm + nlogn, binary search num from A in B. mlogn, total: mlogm + nlogn + mlogn 么？错了哪两个case啊？能看到么

第二题不需要sort两个，只需要sort比较短的数组就可以。时间复杂度是O((m + n) * log (min(m, n)))

请问楼主明白知道是错了那两个test case吗？数组里面的数和target有范围吗? 可以是负数吗? test case会不会错在这里

帖子里面大家就别贴代码了吧，三哥会来看的。二楼说的解法是对的。我自己做的时候漏掉了一些解。提交完OA我自己就想到该怎么做了，做的时候脑子不转。。。还是面的太少了

signalwolf 发表于 2018-12-17 12:40
[mw_shl_code=python,true]from random import randint

from bisect import bisect_left

你这个解法是对的。以后别贴代码了，外国人会看

zenki 发表于 2018-12-18 00:41
你这个解法是对的。以后别贴代码了，外国人会看

是么，我都不知道。多谢提醒，以后不发了 :)