数据结构 | 每日一练（71）
数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 0(n)、空间复杂度为 0(1)的算法， 该算法删除线性表中所有值为 item 的数据元素。（O（1）表示算法的辅助空间为常量）。
递增有序。
正确答案
PS：||代表注释
1．[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右
端元素左移至值为item的数据元素位置。
void Delete（ElemType A[ ]，int n）∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。
{i=1；j=n；∥设置数组低、高端指针（下标）。
while（i<j）
{while（i<j && A[i]!=item）i++； ∥若值不为item，左移指针。
if（i<j）while（i<j && A[j]==item）j--；∥若右端元素值为item，指针左移
if（i<j）A[i++]=A[j--]；
}
[算法讨论] 因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-28，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读