- 题目描述 存在一个数列的某种排列。
- 现在已知数列中每个数的大小 arr1 ,和每个数之前有多少个比它自身小的数 arr2,要求恢复出原来的排列。保证数列中的元素两两不等。
- 思路点拨 先将所有数按从大到小的顺序排列,然后从最大的开始插入到线段树中。对于区间 [l,mid],[mid,r]。
- 满足[l,mid]中未被填充的数字比比它自身小的数的个数大,则继续搜索左区间,反之搜索右区间。
- 填充,更新即可。
- 时间复杂度为O(nlogn)。
010-64736641
intl.apac.cn.aic@disney.com
北京市朝阳区望京东园四区13号楼-4至33层101内B座21层2101-2108室、22层2201-2208室
小程序
公众号
APP