PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 中介數編解碼

看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間12年前 (2012/02/07 00:35)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《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