作者osnq (又可以挂bbs了)
看板Programming
标题[讨论] LeetCode 1649. Create Sorted Array thr
时间Sat Dec 9 08:05:25 2023
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://webptt.com/cn.aspx?n=bbs/Programming/M.1702080327.A.6F9.html
1F：推 seanwu: 你回圈里对vector的emplace最差会是O(N) 125.229.71.95 12/09 20:58
2F：→ seanwu: 乘起来是O(N^2) 125.229.71.95 12/09 20:59
3F：→ seanwu: 如果你想用现在的方向(计数,插入)去做， 125.229.71.95 12/09 21:13
4F：→ seanwu: 那大概会需要线段树这类的资料结构 125.229.71.95 12/09 21:13
5F：→ osnq: 原来是插入, 我一直以为是找位置. 感谢大大~ 118.166.111.55 12/09 22:23
6F：推 seanwu: btw, 这题看起来是经典逆序数对的变形， 125.229.71.95 12/09 23:22
7F：→ seanwu: 类似的方法应该也可以解 125.229.71.95 12/09 23:22