f*********d
发帖数: 140 | 1 考古到了一道老题~ 不会做~
给定一个数字数组，其中每个元素是从末端数小于原数组中该元素的个数。
求原数组。原数组中元素是从1到n。
Example:
原数组:4,1,3,2
Count array:3,0,1,0 | z****e
发帖数: 54598 | 2 从后往前扫一遍
每次list.add(count[i],object[i]) | P**l
发帖数: 3722 | 3 肯定得从前往后扫啊。
输入的最后一个数肯定是0吧
【在 z****e 的大作中提到】
: 从后往前扫一遍
: 每次list.add(count[i],object[i])
| z****e
发帖数: 54598 | 4 that's exactly what i need
add(0,object) == add(object) where list.size()==0
【在 P**l 的大作中提到】
: 肯定得从前往后扫啊。
: 输入的最后一个数肯定是0吧
| f*********d
发帖数: 140 | 5 恕我驽钝~ 没看懂~
能稍微详细一点吗？
count[i] 和 object[i] 都是什么啊？
输入只有count array
【在 z****e 的大作中提到】
: 从后往前扫一遍
: 每次list.add(count[i],object[i])
| z****e
发帖数: 54598 | 6 count == count array
object == Integer array
and method:
List.add(int index, Object element)
【在 f*********d 的大作中提到】
: 恕我驽钝~ 没看懂~
: 能稍微详细一点吗？
: count[i] 和 object[i] 都是什么啊？
: 输入只有count array
| p*****2
发帖数: 21240 | | z****e
发帖数: 54598 | 8 Integer == previous index number
index: 0,1,2 - for(int i=0;i...;i++)
count: 1,1,0 - input data
numb: 2,3,1 - what we want
list.add(0,2); - [2]
list.add(1,1); - [2,1]
list.add(1,0); - [2,0,1]
then
map {{2,1},{0,2},{1,3}}
sort by key and get the value
[0,1,2] -> [2,3,1]
【在 f*********d 的大作中提到】
: 恕我驽钝~ 没看懂~
: 能稍微详细一点吗？
: count[i] 和 object[i] 都是什么啊？
: 输入只有count array
| f*********d
发帖数: 140 | 9 学习了，多谢大牛指教~
【在 z****e 的大作中提到】
: Integer == previous index number
: index: 0,1,2 - for(int i=0;i...;i++)
: count: 1,1,0 - input data
: numb: 2,3,1 - what we want
: list.add(0,2); - [2]
: list.add(1,1); - [2,1]
: list.add(1,0); - [2,0,1]
: then
: map {{2,1},{0,2},{1,3}}
: sort by key and get the value
| p****g
发帖数: 355 | 10 米高蜥蜴的解法有点意思，我还以为只能从前面来。学习了。
设有list{1，2，3，4}，Count array:3,0,1,0 代表了每个数在剩余list中的位置
位置3-〉4，剩余list{1，2，3}
位置0-〉1，剩余list{2，3}
位置1-〉3，剩余list{2}
位置0-〉2，剩余list{} | | | r*********n
发帖数: 4553 | 11 贴一个代码。这个复杂度是O（N^2），原因是set::iterator是bidirectional，
所以下面这一行是linear time：
auto it = advance(num.begin(), A[i])
如果要得到O(NlogN)，需要set提供 iterator select(int rank) 这个API，
auto it = num.select(A[i])
其实BST稍微改一下就可以实现select（可惜STL set没这个method），复杂度是O(logN
)。
vector original_arr(const vector& A){
vector ret;
if( A.empty() ) return ret;
ret.resize(A.size());
set num;
for(int i = 1; i <= A.size(); i++){
num.insert(i);
}
for(int i = 0; i < A.size(); i++){
auto it = advance(num.begin(), A[i]);
ret[i] = *it;
num.erase(it);
}
return ret;
} | h****p
发帖数: 87 | | p*****2
发帖数: 21240 | 13
我觉得n^2不难想。不知道能不能再优化。
【在 h****p 的大作中提到】
: 这题没碰到过 不太好想啊
| n**********e
发帖数: 45 | 14 simple python implementation:
F = []
for i in range(0,len(countArray)):
ct = countArray[i] + 1
F_cp = F[:]
F_cp.sort()
for j in F_cp:
if j <= ct:
ct = ct + 1
F.append(ct) | n**********e
发帖数: 45 | 15 n Log(n) improvement (pseudo codes):
F = []
F_cp = []
for i in range(0,len(countArray)):
ct = countArray[i] + 1
binary_find j so that F_cp[j] < ct #F_cp is always sorted
ct += (j+1)
while F_cp[j+1] == ct:
j += 1
ct += 1
F_cp.insert(ct) at j
F.append(ct)
【在 n**********e 的大作中提到】
: simple python implementation:
: F = []
: for i in range(0,len(countArray)):
: ct = countArray[i] + 1
: F_cp = F[:]
: F_cp.sort()
: for j in F_cp:
: if j <= ct:
: ct = ct + 1
: F.append(ct)
|
|
