G家on-site的一道题讨论

给一个数组，里面是每个人的身高。要求对每个人，计算前面有多少人比他高。要求返回所有人的总数。我首先说用两个for loop, 但是时间复杂度太高。要维护一个排序

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

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

维护一个balanced tree, 是的操作都是logn. 不知道大家有什么想法。

lc315吧，常规做法就mergesort了

二叉搜索求插入位置？

1. class HeightCalcuation:
   
2.   def M1(self, nums):
   
3.     if len(nums) <= 1:
   
4.       return 0
   
5.     res = 0
   
6.     newarr = [nums[0]]
   
7.     for i in range(1, len(nums)):
   
8.       l, r = 0, len(newarr)
   
9.       while l < r:
   
10.         mid = (l + r)//2
    
11.         if newarr[mid] < nums[i]:
    
12.           l = mid + 1
    
13.         else:
    
14.           r = mid
    
15.       res += len(newarr)- l
    
16.       newarr.insert(l, nums[i])
    
17.     return res

复制代码

dengzeyu147 发表于 2019-9-15 04:29
我觉得lc 315的bst解法 在面试中会比较容易实现，但是bst最坏情况的时间复杂度是n平方，

n^2肯定不行的，那这题要求也太低了，最好的解法应该是Merge Sort

这是leetcode 原题。用greedy 的想法先排高的人，再排矮的人。因为矮的人在高的人眼里就是隐形的。矮的人前面有几个比自己高的就暂时排在第几。

用merge sort，一边排序，一边记录对于右半边每一个点，左半边有几个值小于他。

linglz3 发表于 2019-9-14 12:43
这是leetcode 原题。用greedy 的想法先排高的人，再排矮的人。因为矮的人在高的人眼里就是隐形的。矮的人前 ...

求问题号，是在找不到，谢谢

strawberry008 发表于 2019/09/14 13:12:32


求问题号，是在找不到，谢谢

leetcode 406

用segment tree，按顺序插入查询

如果要实现平衡BST那就只好背代码了，没人可以45分钟从头推出来一个BST吧。

我喜欢用binary index tree， 在topcoder上的tutorial学到的

https://www.topcoder.com/communi ... nary-indexed-trees/
问这么难的题， 太不友好了。

lld2019 发表于 2019-9-14 13:45
我喜欢用binary index tree， 在topcoder上的tutorial学到的

https://www.topcoder.com/communi ... nar ...

我觉得这个题 bst实现简单点？