※ 引述《tropical72 (蓝影)》之铭言： : 下述说明, array index start from 0. : 不知道这有没有明确定义的名词 < 其实是在排列演算法里面看到的 >。 : 现假设一 arr[] = {6,3,4,5,1,2}; : 中介数 n[i] 代表 arr[i] > arr[j] ( for j>i) 之个数， : 白话点，就是元素 a[i] 以右，比 a[i] 还大的个数。 : 以 n[1] 为例，arr[1] 右边比 arr[1] 大的数有 2 个， n[1]=2； : n[2] ,arr[2] arr[2] 1 , n[2]=1。 : ---- : 这里做几个前提假设 : a. 假设 array 数值分布为 [1,n] 或 [0,n-1] : b. 每个数都刚好会出现一次。 : 问题有三个 : 1. 有办法快速知道 n[] 值吗？ (可接受额外空间) : 目前作法是 : : for(i=0; i<size; ++i) : for(n[i]=0, j=i+1; j<size; ++j) : n[i]+=(arr[j]>arr[i]); : 因这动作非常频繁，不知是否有其他作法？ 硬爆: 把动作抽象化：我们需要一个支援如下操作的集合S - 动态增(删)一个数字 - 查询比 k 小的数字有几个 那上述回圈改为 S ← {} for i = n down to 1 n[i] = 查询 S 中有几个数字 < a[i] 把 a[i] 加入 S S可以用平衡树或Binary Index Tree(BIT, 好写)实现. 或者, BIT 可以维护 [1,i] i≦n 的资讯, 也可以变成维护 [i,n], 1≦i 我们把 a[] 的数字由小到大处理 v[1...n] = 0 for k = 1 to n let a[i] be the kth smallest number in a[] n[i] = 求和: v[i+1...n] v[i]++ 其中 v 可以用 segment tree(???这名称我不确定 反正对岸称为线段树)或 BIT 维护 其实跟上面方法一样意思...... : 2. 怎麽再解码回去？ (可接受额外空间) : 若 n[] = {1,0,2,1 } ; 我该怎麽解码解成 : arr[] = {4,5,3,1,2} 或 {3,4,2,0,1}？ : const int size=5; : char used[size]={0}; : int i, j, cnt; : for(i=0; i<size-1; ++i){ : cnt = 0; : for(j=size-1; cnt!=n[i]; --j) : if(used[j]==0) ++cnt; : arr[i] = j, used[j]=1; : } : // 最後还要查一次没用到的 : for(i=0; i<size && used[i]; ++i) ; : arr[size-1] = i; : 目前想法也是猪头想法，只差无限猴子定理没搬出来做， : 不知能否有些技巧？ 一样,把要什麽动作写出来可以知道哪边可以加速 (注:这个同 http://uva.onlinejudge.org/external/115/11525.html ) S = {1, 2, ..., n} n[] 为输入的编码 for i = 1...n a[i] ← S 中第 n[i] 小的数字 从 S 中移除 a[i] 所以我们的 S 需要: - 求出第 k 大的数字是什麽 - 删除任一个数字 一样, S 用任一种平衡树都可以, 用 segment tree 也可以, BIT 上二分搜也可以 BIT上二分搜大致是: BIT纪录<=k的数字有几个, 然後对这个二分搜找到所需的数字是谁 附上以前写的程式码, 但是当时乱写的, 只是稍微加快了原先 O(n^2) 的算法, 并不是 O(n lg n) / O(n lg n lg n) 的做法... http://pastie.org/3328428 当时记的好像是"已经删掉了几个数" : 3. 假设不成立时，中介数之编解码是否该重新设计？ : 倘若 假设 a. array 数值分布为 [1,n] 或 [0,n-1] 不成立， : 唯一确定的是 array 元素保证两两相异，试问还有什麽技巧可完成？ 预处理把 a 中每个数字是第几大的算出来, 范围就变 [1,n] : ---- : 这篇发得很像作业文，但纯粹是个人进修卡住， : 希望各位先进能不吝给个意见。 : 恳请不吝赐教，小弟感激不尽。 突然发现跟 #1E06h4Uk 有类似处... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.33.242