3. 有一个整数顺序表工。设计一个尽可能高效的算法删除其中所有值为负整数的元素(假设工中值为负整数的元素可能有多个)，删除后元素的相对次序不改变。并给出算法的时间和空间复杂度。

为了高效地删除整数顺序表中所有负整数元素，可以采用双指针法。遍历列表的同时，使用两个指针，一个指向当前正在检查的元素，另一个指向下一个需要保留的位置。当遇到非负整数时，将该元素移到已检查区域的末尾，并同时更新实际位置指针。遍历完成后，实际位置指针所指的位置就是新列表的结尾。

以下是伪代码描述：

def deleteNegativeIntegers(arr):
    if not arr: return []  # 如果数组为空，直接返回空
    start = 0  # 用于记录非负元素起始位置
    for i in range(len(arr)):
        if arr[i] >= 0:  # 遇到非负数
            arr[start] = arr[i]
            start += 1
    return arr[:start]  # 返回切片，只包含非负部分

# 时间复杂度分析：
# - 最坏的情况下，我们需要遍历整个数组一次，所以时间复杂度是 O(n)，n 是原数组长度。
# - 空间复杂度分析：
#   - 因为我们仅复制了非负元素，最坏情况是数组全为负数，则空间复杂度是 O(1)（因为我们没有额外的空间消耗）；
#   - 如果数组中有非负元素，则空间复杂度是 O(m)，m 是非负元素的数量，但平均来说接近 O(1)。

相关问题

3. 有一个整数顺序表工。设计一个尽可能高效的算法删除其中所有值为负整数的元素(假设工中值为负整数的元素可能有多个),删除后元素的相对次序不改变。并给出算法的时间和空间复杂度。使用Java编写

为了高效地删除整数列表 `nums` 中所有值为负数的元素，你可以采用“双指针”策略，同时遍历列表，只保留非负数。这种做法不需要额外的空间存储，时间复杂度主要取决于列表的实际长度以及负数的数量。

算法步骤如下：

1. 定义两个指针 `left` 和 `right`，初始时都指向列表的第一个元素。
2. 当 `left` 指向的元素是非负数时，将其移动到新的位置（即 `right++`）。
3. 如果 `left` 指向的是负数，不做处理，直接 `left++`，继续检查下一个元素。
4. 当 `left` 越过所有负数后，将 `nums` 切片从 `right` 开始，直到列表结束，得到的就是去除了负数的新列表。

以下是这个算法的 Java 实现：

public class Solution {
    public void removeNegativeNumbers(int[] nums) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] >= 0) {
                nums[left++] = nums[right]; // 移动非负数到新位置
            }
        }
        // 简化数组大小
        nums = Arrays.copyOfRange(nums, left, nums.length);
    }
}

时间复杂度：O(n)，n 是列表 `nums` 的长度。因为每个元素只会被访问一次。

空间复杂度：O(1)，因为我们只是在原数组上移动元素，没有使用额外的空间。

有一个整数顺序表L，设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个)， * 删除后元素的相对次序不改变，并给出算法的时间和空间复杂度

可以使用双指针法，一个指针指向当前需要删除的位置，另一个指针向后扫描，遇到正整数就将其赋值给第一个指针所指向的位置，同时第一个指针向后移动一位。最后将第一个指针所指向的位置及其后面的元素全部删除即可。

时间复杂度为O(n)，空间复杂度为O(1)。

代码示例（Python）：

def remove_negative(L):
    i = 0
    for j in range(len(L)):
        if L[j] >= 0:
            L[i] = L[j]
            i += 1
    del L[i:]

L = [1, -2, 3, -4, 5, -6]
remove_negative(L)
print(L)  # [1, 3, 5]