已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素

可以采用双指针法来解决这个问题，假设我们有两个指针i和j，初始时i等于0，j等于1。我们遍历顺序表，每次将当前元素保存到一个新的列表B中，并检查它是否与前一个元素（即B[j-1]）相同。

1. 如果当前元素A[i]与B[j-1]不同，说明这是新的值，将A[i]添加到B并移动j到下一个位置，j = j + 1。
2. 如果当前元素A[i]与B[j-1]相同，表示有重复值，跳过这个元素，不做任何操作，i = i + 1，直到找到不同的元素为止。

当i遍历完整个原序列A后，新列表B就是去重后的序列。这是因为如果两个连续的元素相同，那么在第一个元素之后的所有相同元素都被省略了。

以下是伪代码示例：

function deleteDuplicates(A):
    B = []
    i = 0
    while i < len(A):
        if A[i] != B[-1]:   # 如果A[i]与B的最后一个元素不同
            B.append(A[i])  # 将A[i]加入B
        i = i + 1

    return B

相关问题

已知一个顺序表a，其元素值非递减有序排列，编写一个算法删除表中多余的值相同的元素

在一个非递减有序的顺序表`a`中删除多余的相同元素，可以采用双指针法，同时维护两个指针，一个指向当前元素，另一个用于比较。以下是步骤：

1. 定义两个指针`i`和`j`，初始都设为0，`i`表示正在处理的位置，`j`表示找到的第一个不重复的元素位置。

2. 当`i < a.length`时，执行循环：
- 检查`a[i]`是否等于`a[j]`。如果不等于，则将`a[j+1] = a[i]`并将`j`后移一位。
- 如果相等，继续移动`i`到下一个元素，因为后续所有`a[i]`都是重复的。

3. 循环结束后，`a[j+1]`之后的部分就是去重后的列表，因为`j+1`之后的所有元素都不再有重复的。

4. 返回新的有效长度`j + 1`。

**伪代码示例**:

def removeDuplicates(a):
    i = j = 0
    while i < len(a):
        if a[i] != a[j]:
            j += 1
            a[j] = a[i]
        i += 1
    return j + 1

# 使用示例
newLength = removeDuplicates(a)

C++实现算法，已知一个顺序表A中的元素非递减有序，插入一个元素X，仍然保持非递减有序

在C++中，如果有一个已排序的顺序表（如数组或动态数组），并且新元素X是非递减的，插入到这个有序列表中通常会很简单。以下是基本步骤：

1. **遍历找到插入位置**：
- 初始化两个指针i（开始）和j（结束）。假设列表长度为n，初始时i = 0，j = n - 1。
- 比较待插入元素X与列表中的当前元素A[j]，如果X <= A[j]，说明应在j处或其左侧插入。

2. **二分查找插入位置**：
- 如果X小于等于A[j]，将j减半，并继续比较X与A[j]直到找到一个位置i <= j且X > A[i]，此时i+1就是应该插入的位置。

3. **插入操作**：
- 将元素X插入到索引i+1处，如果使用的是数组，可以像这样操作：`A[i+1] = X;`
- 如果使用动态数组，需要移动后续元素并更新数组大小。

4. **更新边界**：
- 对于动态数组，可能还需要调整数组的实际容量以容纳新的元素。

下面是一个简单的示例代码片段：

// 假设A是一个已排序的整数动态数组
void insert(int& A[], int size, int x) {
    if (size == 0 || x >= A[size - 1]) { // 如果插入位置在末尾或者x大于最后一个元素
        A[size] = x;
        size++;
    } else {
        int i = 0, j = size - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (x <= A[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        std::swap(A[i], x); // 将元素放在正确位置
    }
}