给你一个包含若干 互不相同 整数的数组 nums ,你需要执行以下操作 直到数组为空 : 如果数组中第一个元素是当前数组中的 最小值 ,则删除它。 否则,将第一个元素移动到数组的 末尾 。 请你返回需要多少个操作使 nums 为空。时间复杂度为nlogn
时间: 2024-04-30 15:18:03 浏览: 71
可以使用一个优先队列(最小堆)来维护当前数组中的最小值。首先将数组中的元素全部插入优先队列中,然后每次取出队列的最小值,如果它等于数组的第一个元素,则将其删除;否则将数组的第一个元素移到数组末尾。重复这个过程直到数组为空,此时操作的次数就是答案。
由于每次取出队列的最小值的时间复杂度为 O(logn),而最多需要操作 n 次,因此总的时间复杂度为 O(nlogn)。
以下是代码实现:
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
pq.push(nums[i]);
}
int ans = 0;
while (!pq.empty()) {
int x = pq.top();
pq.pop();
if (x == nums[0]) {
ans++;
nums.erase(nums.begin());
} else {
nums.push_back(nums[0]);
nums.erase(nums.begin());
pq.push(x);
}
}
cout << ans << endl;
return 0;
}
```
阅读全文