GUGE面筋

刚出炉的面筋，leetc

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

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

，求过求人品

是求右边比当前数大的有几个吗？

对啊 是求右边比当前大的有几个吗

xavierliu 发表于 2017-10-21 16:15
对啊 是求右边比当前大的有几个吗

是的，i:0-n时index大于i且值大于num[i]的个数

这个题除了用bst还有其他办法吗

感觉这道题好难，没做过的妥妥👻

bst解法:

1. class BSTNode(object):
   
2.     def __init__(self, val):
   
3.         self.left = None
   
4.         self.right = None
   
5.         self.val = val
   
6.         self.cnt = 1
   
7.         self.rightTreeSize = 0
   
8. 
   
9. class BST(object):
   
10.     def __init__(self):
    
11.         self.root = None
    
12. 
    
13.     def insert(self, root, target):
    
14.         if self.root is None:
    
15.             self.root = BSTNode(target)
    
16.             return None
    
17. 
    
18.         if root is None:
    
19.             return BSTNode(target)
    
20.         if root.val == target:
    
21.             root.cnt += 1
    
22.         elif root.val < target:
    
23.             root.right = self.insert(root.right, target)
    
24.             root.rightTreeSize += 1
    
25.         else:
    
26.             root.left = self.insert(root.left, target)
    
27.         return root
    
28. 
    
29.     def search_count(self, root, target):
    
30.         if root is None:
    
31.             return 0
    
32.         if root.val == target:
    
33.             return root.rightTreeSize
    
34.         elif target > root.val:
    
35.             return self.search_count(root.right, target)
    
36.         else:
    
37.             return root.cnt + root.rightTreeSize + self.search_count(root.left, target)
    
38. 
    
39.     def serilize(self):
    
40.         def helper(root, ret):
    
41.             if root is None:
    
42.                 ret.append('#')
    
43.                 return
    
44.             ret.append(root.val)
    
45.             helper(root.left, ret)
    
46.             helper(root.right, ret)
    
47.             return
    
48.         ret = []
    
49.         helper(self.root, ret)
    
50.         return ret
    
51. 
    
52. 
    
53. def Greater(nums):
    
54.     if len(nums) == 0:
    
55.         return []
    
56. 
    
57. 
    
58.     tree = BST()
    
59.     ret = []
    
60. 
    
61.     for n in nums[::-1]:
    
62.         tree.insert(tree.root, n)
    
63.         ret.append(tree.search_count(tree.root, n))
    
64.     return ret[::-1]
    
65. 
    
66. print Greater([1,2,2,3,4,5])
    
67. print Greater([1,1,1])
    
68. print Greater([3,2,1])
    
69. print Greater([1,2])

复制代码

segment tree. 先扫描一遍，设置root的区间，然后依次往里面插入节点。

最优做法是merge sort，保证可以O(nlogn)，其他都不能保证。BST, segment tree or BIT的做法也可以nlogm，但是m是max - min。

不过说实话，这题目没做过一定挂（当然要求是时间复杂度为nlogn）。而且电面面这种题目很坑人啊，没办法画图帮助思考和解释。