给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到数组为空 ：
- 如果数组中第一个元素是当前数组中的 最小值 ，则删除它。
- 否则，将第一个元素移动到数组的 末尾 。
请你返回需要多少个操作使 nums 为空。
示例 1：
输入：nums = [3,4,-1] 输出：5
| Operation | Array |
|---|---|
| 1 | [4, -1, 3] |
| 2 | [-1, 3, 4] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
示例 2：
输入：nums = [1,2,4,3] 输出：5
| Operation | Array |
|---|---|
| 1 | [2, 4, 3] |
| 2 | [4, 3] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
示例 3：
输入：nums = [1,2,3] 输出：3
| Operation | Array |
|---|---|
| 1 | [2, 3] |
| 2 | [3] |
| 3 | [] |
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109nums中的元素 互不相同 。
方法一：哈希表 + 排序 + 树状数组
我们先用哈希表
接下来，我们遍历排序后的数组
遍历结束后，返回操作数
时间复杂度
from sortedcontainers import SortedList
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
pos = {x: i for i, x in enumerate(nums)}
nums.sort()
sl = SortedList()
ans = pos[nums[0]] + 1
n = len(nums)
for k, (a, b) in enumerate(pairwise(nums)):
i, j = pos[a], pos[b]
d = j - i - sl.bisect(j) + sl.bisect(i)
ans += d + (n - k) * int(i > j)
sl.add(i)
return ansclass BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
pos = {x: i for i, x in enumerate(nums)}
nums.sort()
ans = pos[nums[0]] + 1
n = len(nums)
tree = BinaryIndexedTree(n)
for k, (a, b) in enumerate(pairwise(nums)):
i, j = pos[a], pos[b]
d = j - i - tree.query(j + 1) + tree.query(i + 1)
ans += d + (n - k) * int(i > j)
tree.update(i + 1, 1)
return ansclass BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= x & -x;
}
return s;
}
}
class Solution {
public long countOperationsToEmptyArray(int[] nums) {
int n = nums.length;
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; ++i) {
pos.put(nums[i], i);
}
Arrays.sort(nums);
long ans = pos.get(nums[0]) + 1;
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int k = 0; k < n - 1; ++k) {
int i = pos.get(nums[k]), j = pos.get(nums[k + 1]);
long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
ans += d + (n - k) * (i > j ? 1 : 0);
tree.update(i + 1, 1);
}
return ans;
}
}class BinaryIndexedTree {
public:
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x) {
s += c[x];
x -= x & -x;
}
return s;
}
private:
int n;
vector<int> c;
};
class Solution {
public:
long long countOperationsToEmptyArray(vector<int>& nums) {
unordered_map<int, int> pos;
int n = nums.size();
for (int i = 0; i < n; ++i) {
pos[nums[i]] = i;
}
sort(nums.begin(), nums.end());
BinaryIndexedTree tree(n);
long long ans = pos[nums[0]] + 1;
for (int k = 0; k < n - 1; ++k) {
int i = pos[nums[k]], j = pos[nums[k + 1]];
long long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
ans += d + (n - k) * int(i > j);
tree.update(i + 1, 1);
}
return ans;
}
};type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func countOperationsToEmptyArray(nums []int) int64 {
n := len(nums)
pos := map[int]int{}
for i, x := range nums {
pos[x] = i
}
sort.Ints(nums)
tree := newBinaryIndexedTree(n)
ans := pos[nums[0]] + 1
for k := 0; k < n-1; k++ {
i, j := pos[nums[k]], pos[nums[k+1]]
d := j - i - (tree.query(j+1) - tree.query(i+1))
if i > j {
d += n - k
}
ans += d
tree.update(i+1, 1)
}
return int64(ans)
}class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
public update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] += v;
x += x & -x;
}
}
public query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
function countOperationsToEmptyArray(nums: number[]): number {
const pos: Map<number, number> = new Map();
const n = nums.length;
for (let i = 0; i < n; ++i) {
pos.set(nums[i], i);
}
nums.sort((a, b) => a - b);
const tree = new BinaryIndexedTree(n);
let ans = pos.get(nums[0])! + 1;
for (let k = 0; k < n - 1; ++k) {
const i = pos.get(nums[k])!;
const j = pos.get(nums[k + 1])!;
let d = j - i - (tree.query(j + 1) - tree.query(i + 1));
if (i > j) {
d += n - k;
}
ans += d;
tree.update(i + 1, 1);
}
return ans;
}