若一个线性表l采用顺序存储结构存储,其中所有的元素为整数。设计一个算法,删除元素值在[x,y]之间的所有元素,要求算法的时间复杂度为o(n),空间复杂度为o(1)。
时间: 2023-06-05 09:47:21 浏览: 265
已知线性表按顺序存于内存,每个元素都是整数,试设计把所有值为负数的元素移到全部正数值元素前边的算法 .cpp
算法思路如下:
1. 初始化两个指针i和j,分别指向线性表的第一个元素和第二个元素。
2. 从第二个元素开始遍历线性表,如果当前元素的值在[x,y]之间,则j指针后移一位,否则将元素复制到i指针所指位置,i指针后移一位。
3. 遍历完线性表后,线性表的长度为i,其中[0,i-1]区间内的元素为最终结果。
时间复杂度O(n),空间复杂度O(1)
阅读全文