📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 孤笑客
跳转到指定楼层
上一主题 下一主题
收起左侧

请教4道题目的最优做法(G家真题)

🔗
ryancooper 2015-10-31 01:52:12 | 只看该作者
全局:
小A要当码农 发表于 2015-10-30 23:45
请问楼主,BST的话你打算如何实现呢?以及如何将元素在树中的位置和比他大的元素个数联系起来呢?谢谢

我不是LZ,但我先问答你吧。对于那个个数,你可以在你自己创建的结点中maitain一个子树的size这样一个量。这样你就可以知道比一个元素大的个数有多少了。然后Balanced BST的话,一般的实现都比较繁琐。如果你真要手写,可以尝试Treap。它是一种randomized的数据结构,写起来比普通的BST复杂不了多少,但是实际运行时间复杂度和平衡树差不多。
回复

使用道具 举报

全局:
ryancooper 发表于 2015-10-31 01:52
我不是LZ,但我先问答你吧。对于那个个数,你可以在你自己创建的结点中maitain一个子树的size这样一个量 ...

谢谢你的解答。这道题我的第一想法也是用BST,但是觉得那么短的时间内,熟练度不够的话,怕实现不了
回复

使用道具 举报

🔗
ryancooper 2015-10-31 07:51:35 | 只看该作者
全局:
小A要当码农 发表于 2015-10-31 02:43
谢谢你的解答。这道题我的第一想法也是用BST,但是觉得那么短的时间内,熟练度不够的话,怕实现不了

还有一种做法,你可以用类似counting inversions的方法来做。
回复

使用道具 举报

全局:
ryancooper 发表于 2015-10-31 07:51
还有一种做法,你可以用类似counting inversions的方法来做。

类似于LC里面H-index那道题吗?
回复

使用道具 举报

🔗
ryancooper 2015-10-31 12:27:17 | 只看该作者
全局:
小A要当码农 发表于 2015-10-31 09:45
类似于LC里面H-index那道题吗?

和那个不一样。具体是什么你可以参考算法导论第二章习题2-4
回复

使用道具 举报

全局:
ryancooper 发表于 2015-10-31 12:27
和那个不一样。具体是什么你可以参考算法导论第二章习题2-4

好的!太厉害啦~赞一个👍
回复

使用道具 举报

🔗
kanone 2015-11-4 16:32:24 | 只看该作者
全局:
ryancooper 发表于 2015-10-31 12:27
和那个不一样。具体是什么你可以参考算法导论第二章习题2-4

厉害!感觉这个才是此题的标准答案。终于折腾出来了,代码如下(Python):

Analysis:

counting greater elements in the right side, which could be converted to counting
greater elements in the left side of the reversed array, then we can use counting
inversions method mentioned in Problem 2-4 of [Introduction to Algorithms].

Generally speaking, I used a revised version of merge sort to count inversions.


  1. def f(nums):
  2.    
  3.     """
  4.     this array stores final results
  5.     """
  6.     result = [0] * len(nums)

  7.     """
  8.     each element in this array indicates the index of result,
  9.     so that no matter in what order the array A is, we could locate the
  10.     number of inversions in array result
  11.     """
  12.     index_of_result = [x for x in range(len(nums))]   
  13.    
  14.     """
  15.     reverse the original array nums   
  16.     """
  17.     A = nums.copy()
  18.     A.reverse()
  19.    
  20.     """
  21.     merge inversion procedure starts   
  22.     """   
  23.     mergesort(A, 0, len(A) - 1, result, index_of_result)
  24.    
  25.     """
  26.     restore the original order   
  27.     """
  28.     result.reverse()
  29.    
  30.     return result
  31.    

  32. def mergesort(A, p, r, res, ind):
  33.    
  34.     if p == r:
  35.         return 0
  36.    
  37.     q = (p + r) // 2
  38.     mergesort(A, p, q, res, ind)
  39.    
  40.     mergesort(A, q + 1, r, res, ind)
  41.    
  42.     merge(A, p, q, r, res, ind)
  43.    

  44.    
  45. def merge(A, p, q, r, res, ind):
  46.    
  47.     L = A[p:q + 1]
  48.     R = A[q + 1:r + 1]

  49.     """
  50.     resL and resR store indexes of left and right side of result array     
  51.     """
  52.     resL = ind[p:q + 1]
  53.     resR = ind[q + 1:r + 1]
  54.    
  55.     k = p
  56.     i = j = 0
  57.     while i <= q - p and j <= r - q - 1:
  58.         if L[i] <= R[j]:
  59.             A[k] = L[i]
  60.             ind[k] = resL[i]
  61.             i += 1
  62.             
  63.         else:
  64.             A[k] = R[j]
  65.             ind[k] = resR[j]
  66.             
  67.             """
  68.             modify corresponding element in result array            
  69.             """
  70.             res[ind[k]] += len(L) - i
  71.             j += 1
  72.             
  73.         k += 1
  74.     if j <= r - q - 1:
  75.         A[k:r + 1] = R[j:]
  76.         ind[k:r + 1] = resR[j:]
  77.     if i <= q - p:
  78.         A[k:r + 1] = L[i:]
  79.         ind[k:r + 1] = resL[i:]
  80.    
复制代码
回复

使用道具 举报

🔗
mouse77 2015-11-15 12:25:36 | 只看该作者
全局:
z928czzc 发表于 2015-10-30 00:59
第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下 ...

想问下,第一题怎么做??谢谢
回复

使用道具 举报

🔗
kelong 2015-11-16 01:03:29 | 只看该作者
全局:
[ 本帖最后由 kelong 于 2015-11-16 01:33 编辑 ]\n\n


题目4解法:


首先剔除array中所有>=N的元素,然后从小到大排序。对于最大的元素(假设为array[i]),设A=N-array[i], B=array[i]-1, 然后递归,新的参数为:array=array[0 ... (i-1)], N=max(A, B)。道理是比较显然的,即,要使添加的元素数目最小,那么array中最大的元素一定要使用。而既然使用最大元素(记为m),那么N与m之间的差就全部要能够生成,同时,[1 to m-1]之间的数也要全部能够生成,所以使用max(A, B)进行递归。
回复

使用道具 举报

🔗
kelong 2015-11-16 01:26:05 | 只看该作者
全局:
[ 本帖最后由 kelong 于 2015-11-16 01:32 编辑 ]\n\n[font=Verdana][quote][size=2][url=forum.php?mod=redirect&goto=findpost&pid=2063145&ptid=145981][color=#999999]mouse77 发表于 2015-11-15 12:25[/color][/url][/size]
想问下,第一题怎么做??谢谢[/quote]

把原数组element[]中每一个元素和index加入一个pair数组中(每个元素有first和secondl两个member):pair[i]=<element[i], i>, 然后把pair数组按照其first元素element排序(升序)。那么对于每一个pair的元素pair[k]=<element[i], i>, 它右面有size-k-1个元素比它大,那么对于结果数组ans[], ans[i]=size-k-1。最后返回ans[]。整个过程只需要一次排序, nLog(n),在家一次O(n)遍历得出ans[]。以上假设没有重复元素,如果有重复,简单修改即可
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表