[討論] LeetCode 1649. Create Sorted Array thr
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
推
12/09 20:58,
11月前
, 1F
12/09 20:58, 1F
→
12/09 20:59,
11月前
, 2F
12/09 20:59, 2F
→
12/09 21:13,
11月前
, 3F
12/09 21:13, 3F
→
12/09 21:13,
11月前
, 4F
12/09 21:13, 4F
→
12/09 22:23,
11月前
, 5F
12/09 22:23, 5F
推
12/09 23:22,
11月前
, 6F
12/09 23:22, 6F
→
12/09 23:22,
11月前
, 7F
12/09 23:22, 7F
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
