删除一个数

删除有序数组里的某个元素，和插入正好相反：把它后面的元素整体往前挪一格，盖住它，再把长度减一。

挪动方向是从前往后：

// 删除下标 pos 处的元素，数组原长 n
for (int i = pos; i < n - 1; i++)
    a[i] = a[i + 1];   // 后一个盖到前一个，从前往后
n--;                   // 长度减一

方向和插入相反，道理一样是“别让还没用到的数据被提前覆盖”：删除是“把后面的往前搬”，从前往后搬时，每次要读的 a[i+1] 都还没被动过，安全；若从后往前反而会出错。

一个常考的细节：删除后，原来最后那个位置还有没有值？——还有，是一个“残留的旧值”。我们只是把长度 n 减了 1，逻辑上认为数组只到 a[n-1]（新长度）为止；物理上 a[n]（老末尾）那格并没有被清空，里面还留着搬家前的旧数据。只要以后都用新的长度去遍历，就访问不到它，不影响结果；但如果误用旧长度，就会把这个残留值也算进去。

复杂度同样是 $O(n)$，最坏挪动近整个数组。