列表

详情

2659. 将数组清空

给你一个包含若干 互不相同 整数的数组 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 []

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: long long countOperationsToEmptyArray(vector<int>& nums) { } };

golang 解法, 执行用时: 172 ms, 内存消耗: 8.9 MB, 提交时间: 2023-05-05 17:10:22 

func countOperationsToEmptyArray(nums []int) int64 {
	n := len(nums)
	id := make([]int, n)
	for i := range id {
		id[i] = i
	}
	sort.Slice(id, func(i, j int) bool { return nums[id[i]] < nums[id[j]] })

	ans := n
	for k := 1; k < n; k++ {
		if id[k] < id[k-1] { // 必须多走一整圈
			ans += n - k // 减去前面删除的元素个数
		}
	}
	return int64(ans)
}

java 解法, 执行用时: 47 ms, 内存消耗: 54.5 MB, 提交时间: 2023-05-05 17:10:10 

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        var id = new Integer[n];
        for (int i = 0; i < n; ++i)
            id[i] = i;
        Arrays.sort(id, (i, j) -> nums[i] - nums[j]);

        long ans = n; // 先把 n 计入答案
        for (int k = 1; k < n; ++k)
            if (id[k] < id[k - 1]) // 必须多走一整圈
                ans += n - k; // 减去前面删除的元素个数
        return ans;
    }
}

python3 解法, 执行用时: 172 ms, 内存消耗: 28.2 MB, 提交时间: 2023-05-05 17:09:56 

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        ans = n = len(nums)
        id = sorted(range(n), key=lambda x: nums[x])
        for k, (pre, i) in enumerate(pairwise(id), 1):
            if i < pre:  # 必须多走一整圈
                ans += n - k  # 减去前面删除的元素个数
        return ans

golang 解法, 执行用时: 148 ms, 内存消耗: 9 MB, 提交时间: 2023-05-05 17:09:34 

// 树状数组模板
type BIT []int

// 将下标 i 上的数加一
func (t BIT) inc(i int) {
	for ; i < len(t); i += i & -i {
		t[i]++
	}
}

// 返回闭区间 [1, i] 的元素和
func (t BIT) sum(i int) (res int) {
	for ; i > 0; i &= i - 1 {
		res += t[i]
	}
	return
}

// 返回闭区间 [left, right] 的元素和
func (t BIT) query(left, right int) int {
	return t.sum(right) - t.sum(left-1)
}

func countOperationsToEmptyArray(nums []int) int64 {
	n := len(nums)
	id := make([]int, n)
	for i := range id {
		id[i] = i
	}
	sort.Slice(id, func(i, j int) bool { return nums[id[i]] < nums[id[j]] })

	ans := n // 先把 n 计入答案
	t := make(BIT, n+1) // 下标从 1 开始
	pre := 1 // 上一个最小值的位置，初始为 1
	for k, i := range id {
		i++ // 下标从 1 开始
		if i >= pre { // 从 pre 移动到 i，跳过已经删除的数
			ans += i - pre - t.query(pre, i)
		} else { // 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数
			ans += n - pre + i - k + t.query(i, pre-1)
		}
		t.inc(i) // 删除 i
		pre = i
	}
	return int64(ans)
}

java 解法, 执行用时: 69 ms, 内存消耗: 53.9 MB, 提交时间: 2023-05-05 17:09:18 

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        var id = new Integer[n];
        for (int i = 0; i < n; ++i)
            id[i] = i;
        Arrays.sort(id, (i, j) -> nums[i] - nums[j]);

        long ans = n; // 先把 n 计入答案
        var t = new BIT(n + 1); // 下标从 1 开始
        int pre = 1; // 上一个最小值的位置，初始为 1
        for (int k = 0; k < n; ++k) {
            int i = id[k] + 1; // 下标从 1 开始
            if (i >= pre) // 从 pre 移动到 i，跳过已经删除的数
                ans += i - pre - t.query(pre, i);
            else // 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数
                ans += n - pre + i - k + t.query(i, pre - 1);
            t.inc(i); // 删除 i
            pre = i;
        }
        return ans;
    }
}

// 树状数组模板
class BIT {
    private final int[] tree;

    public BIT(int n) {
        tree = new int[n];
    }

    // 将下标 i 上的数加一
    public void inc(int i) {
        while (i < tree.length) {
            ++tree[i];
            i += i & -i;
        }
    }

    // 返回闭区间 [1, i] 的元素和
    public int sum(int x) {
        int res = 0;
        while (x > 0) {
            res += tree[x];
            x &= x - 1;
        }
        return res;
    }

    // 返回闭区间 [left, right] 的元素和
    public int query(int left, int right) {
        return sum(right) - sum(left - 1);
    }
}

python3 解法, 执行用时: 1956 ms, 内存消耗: 29 MB, 提交时间: 2023-05-05 17:09:04 

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        ans = n = len(nums)  # 先把 n 计入答案
        t = BIT(n + 1)  # 下标从 1 开始
        pre = 1  # 上一个最小值的位置，初始为 1
        for k, i in enumerate(sorted(range(n), key=lambda i: nums[i])):
            i += 1  # 下标从 1 开始
            if i >= pre:  # 从 pre 移动到 i，跳过已经删除的数
                ans += i - pre - t.query(pre, i)
            else:  # 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数
                ans += i - pre + n - k + t.query(i, pre - 1)
            t.inc(i)  # 删除 i
            pre = i
        return ans

# 树状数组模板
class BIT:
    def __init__(self, n):
        self.tree = [0] * n

    # 将下标 i 上的数加一
    def inc(self, i: int) -> None:
        while i < len(self.tree):
            self.tree[i] += 1
            i += i & -i

    # 返回闭区间 [1, i] 的元素和
    def sum(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.tree[i]
            i &= i - 1
        return res

    # 返回闭区间 [left, right] 的元素和
    def query(self, left: int, right: int) -> int:
        return self.sum(right) - self.sum(left - 1)

上一题

© 2025 leetcode.cn