G家on-site的一道题讨论

我觉得lc 315的bst解法 在面试中会比较容易实现，但是bst最坏情况的时间复杂度是n平方，

dengzeyu147 发表于 2019-9-15 04:28
我觉得这个题 bst实现简单点？

BST 怎么能够迅速判断前面有多少个小于它的数呢？ 这个是O(N), 而BIT可以用O(logN)获得结果， 简单肯定是简单， 但是效率就差些

lld2019 发表于 2019-9-15 05:09
BST 怎么能够迅速判断前面有多少个小于它的数呢？ 这个是O(N), 而BIT可以用O(logN)获得结果， 简单肯定是 ...

bst？你看看315的答案就是了 BIT老记不住

二叉搜索求插入位置？

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

😂单调栈不可以吗？

crazycodyman 发表于 2019-9-16 20:07
n^2肯定不行的，那这题要求也太低了，最好的解法应该是Merge Sort

我觉得这可以讨论 取决于面试官的想法，当然是merge sort更好

为啥我觉得楼主讨论的题目和从二楼开始讨论的题目是不一样的呢？

单调栈吧，比较典型的