AI题库 · GESP-C++八级题库
题目分享 #20174
下面 LIS 函数试图求出最长上升子序列的长度,其时间复杂度为?( )
#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
int n = nums.size();
vector<int> tail;
tail.push_back(INT_MIN);
for (int i = 0; i < n; i++) {
int x = nums[i], l = 0, r = tail.size();
while (l < r) {
int mid = (l + r) / 2;
if (tail[mid] < x)
l = mid + 1;
else
r = mid;
}
if (r == tail.size())
tail.push_back(x);
else
tail[r] = x;
}
return tail.size() - 1;
}
A
O(log n)
B
O(n)
C
O(n log n)
D
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。