Lotplace

本人於該blog的全部文章轉移至[LeetCode]1409 Queries on a Permutation With Key – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

題目來源:Queries on a Permutation With Key – LeetCode

題目重點:
給定一數列queries及正整數m，從m裡找出queries[i]的index並且將m的queries[i]移動到最前端，輸出res裏頭包含所有的queries[i]的index

解題思路:
使用Indexed Binary Tree就能達到時間複雜度O(n*log(m))的解法，簡單說就是計算m陣列中的某數字之前的數字量和得出某數字的index，另外還要考量到移到前端這個動作，因此需要保留額外的空間將數字移動到前端更新BIT。

步驟如下:
let n = queries.size()
1.宣告1陣列pos儲存m陣列各數於BIT中的所在index(為求方便因此pos[0]不放值)
2.宣告bit長度為 m + 保留的移動空間(n) + 1 (queries的長度代表會從m找n次index同時移動n次至前端)
3.BIT初始化，邏輯是把當前數字當作delta為1也就是該位置有1個數字，其他部分就如同BIT裡創建一樣，不過這邊的開始位置是從n + 1開始，前面n個必須保留給移動至前端的數字，同時pos裡放入該數字於BIT內的所在位置。
4.走訪queries利用pos[i]找出位置，針對每個數字利用BIT的性質往上走訪直到根為止，即可找出前方共有多少個數字和也就是index，同時將在m中的queries[i]放到最前方，利用第3步的概念也就是delta = 1並且位置為n進行BIT更新就能順利移到前端，這時根據pos[i]找出的位置因為該位置已經減少1個數字所以也要update且delta = -1，n此時要-1以確保下個前端為空，更新pos[queries[i]]於m中的位置。

重複以上4步即可得到解

Example : queries = [3,1,2,1] , m = 5

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int n = queries.size();
        vector <int> pos(m + 1);
        vector <int> bit(m + n + 1);
        vector<int> res;
        for(int i = 1; i <= m; i++) {
            pos[i] = i + n;
            updateBIT(bit,i + n,1);
        }
        for(int q : queries) {
            res.push_back(getSumBIT(bit,pos[q] - 1));
            updateBIT(bit,pos[q],-1);
            pos[q] = n;
            updateBIT(bit,n--,1);
        }
        return res;
    }
private:
    void updateBIT(vector <int> &bit,int index,int delta) {
        while(index < bit.size()) {
            bit[index] += delta;
            index += index & -index;
        }
    }
    int getSumBIT(vector <int> &bit,int index) {
       int sum = 0;
        while(index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
};

時間複雜度:O(N*log(M))

ghost

Filed under: LeetCode - @ 2021 年 9 月 11 日 下午 5:27

標籤: LeetCode