数据结构题目5：删除表中数据信息为item的元素

题目：已知长度为n的顺序表A，请写出删除该表中数据信息为item的数据元素。
解题思路1：简单粗暴法，从表中的第1个数据元素开始到表中的最后一个数据元素结束，依次将个数据元素与item进行比较，当遇到与item相匹配的数据元素时，随机删除它。
具体算法实现：

var arr = [4,2,5,7,9,6,4,3,2,6,8]
function deleteItemByItem (A, item) {
    let i = 0
    let n = A.length
    while( i<n ){
        if ( A[i]==item ) {
            n = deleteList(A, i+1).length
        } else {
            i++
        }
    }
    return A
}
deleteItemByItem(arr, 2)

其中，deleteList(A, i+1)见删除长度为n的线性表A的第i个数据元素
性能：我们知道算法deleteList(A, i+1)的时间复杂度为O(n)，因而上述的时间复杂度为O(n2)。
那我们可否对算法改进，得到一个时间复杂度为O(n)的算法呢？

解题思路2：设置一个整形变量k，令其初值为-1。在对表中第一个数据元素到最后一个数据元素比较的过程中，当A[i]满足条件时，只将i的值增1，不做其他动作；当A[i]不满足条件时，将A[i]送表中位置i-k-1处。最后修改线性表的长度为n-k-1即可。
算法实现如下：

var arr = [4,2,5,7,9,6,4,3,2,6,8]
function deleteItemByItem (A, item) {
    let i, k=-1
    let n=A.length
    for( i=0; i<n; i++ ){
        if ( A[i]==item ) {
            k++
        } else {
            A[i-k-1] = A[i]
        }
    }
    A.length = A.length - k -1
    return A
}
deleteItemByItem(arr, 2)

性能： 时间复杂度为O(n)