B********a
发帖数: 110 | 1 给定一个数字数组 ，其中每个元素是从末端数小于原数组中该元素的个数。求原数组
。原数组中元素是从 1 到 n。
Example:
原数组 4,1, 3, 2
Count array 3, 0, 1, 0
这题有没有比n^2更快的解法？ | h*****n
发帖数: 188 | 2 Can't tell for sure.
Probably use interval tree or segment tree can achieve o(NlogN).
No sure about those either.
【在 B********a 的大作中提到】
: 给定一个数字数组 ，其中每个元素是从末端数小于原数组中该元素的个数。求原数组
: 。原数组中元素是从 1 到 n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 这题有没有比n^2更快的解法？
| v***d
发帖数: 51 | 3 有一个想法不知道是否可行。
从右到左，建立一个BST。如果在第i步中遇到countArray[i] = k，就把BST分裂成两个
：新建一个父节点，左边是k个元素，右边是i-k个元素。父节点赋值大于左边子树，小
于右边子树（也许值不一定是整数）。顺序记录这些新建节点的值，最后转换成1...n
的值。应该能有O(n*logn)的复杂度吧。 | b*******y
发帖数: 2048 | 4 排序查找
nlogn+n
?
【在 B********a 的大作中提到】
: 给定一个数字数组 ，其中每个元素是从末端数小于原数组中该元素的个数。求原数组
: 。原数组中元素是从 1 到 n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 这题有没有比n^2更快的解法？
|
|
