网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
noip吧 关注：25,171贴子：642,096
  • 4回复贴，共1页

求教，给自然数1到n的随机排列，有没有办法在O(N)求出它的字典序

rt


康拓展开


求康拓展开需要求“右边有几个数比我小”，等价于求逆序对。吾等蒟蒻暂时只有O(nlogn)的方法。
如果N很大，这个字典序的数也很大，即使O(n)求出又有什么用？


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 4回复贴，共1页
分享到: