[討論] LeetCode 1649. Create Sorted Array thr

[osnq (又可以掛bbs了)]

1649. Create Sorted Array through Instructions

請教各位關於這一題,
研究過 solution 與 editorial, 大概就是需要 O(nlog n) 才會過.
因為 input 的關係, 所以要搜尋到正確的位置 insert 就得用 binary search

只是... 還是發生了TLE...
下面是我的 solution, 應該是 O(nlog n).
還請大家幫忙釋疑解惑, 一起討論一下. 謝謝大家.

const int mod = 1e9 + 7;

int createSortedArray(vector<int>& instructions)
{
    int ans = 0;

    int l = 0;
    int r = 0;
    int left = 0;
    int right = 0;
    int n = instructions.size();

    vector<int> nums;

    for (int i = 0; i < n; i++)
    {
        if (nums.size() < 1) {
            nums.push_back(instructions[i]);
            continue;
        }

        l = lower_bound(nums.begin(), nums.end(), instructions[i]) - nums.begin();
        r = upper_bound(nums.begin(), nums.end(), instructions[i]) - nums.begin();

        left = l;
        right = nums.size() - r;

        ans += min(left, right);
        ans = ans % mod;

        nums.emplace(nums.begin() + left, instructions[i]);
    }

    return ans;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.111.55 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1702080327.A.6F9.html
推 seanwu: 你迴圈裡對vector的emplace最差會是O(N)
→ seanwu: 乘起來是O(N^2)
→ seanwu: 如果你想用現在的方向(計數,插入)去做，
→ seanwu: 那大概會需要線段樹這類的資料結構
→ osnq: 原來是插入, 我一直以為是找位置. 感謝大大~
推 seanwu: btw, 這題看起來是經典逆序數對的變形，
→ seanwu: 類似的方法應該也可以解