2.2.3, 4
- 跟第3题一样的解法
- 时间复杂度O(n)，空间复杂度O(1)
void del_st(SqList &list, int s, int t) { if (s >= t || list.length == 0) { cout << "ERROR!" << endl; return; } // 1.要保存的值都放在前面 int k = 0; for (int i = 0; i < list.length; i++) { if (list.data[i] < s || list.data[i] > t) { list.data[k++] = list.data[i]; } } // 2.直接扔掉后面的值 list.length = k; } 复制代码
- 王道答案：自找麻烦的做法
- 有序 -> 从头循环找
>= s，继续找>t的元素 - 一次循环，或者找t从后往前再循环一次
while+++真的非常好用，最好像我这样：先-1然后用前++- 时间复杂度O(n)，空间复杂度O(1)
void del_st2(SqList &list, int s, int t) { if (s >= t || list.length == 0) { cout << "ERROR!" << endl; return; } // 1.找到大于等于s的值 int i = -1; while (list.data[++i] < s); // 2.如果全部元素均小于s if (i >= list.length) { cout << "ERROR!" << endl; return; } // 3.找到大于t的元素 int j = i-1; while (list.data[++j] <= t); // 4.前移，直接占住被删元素的位置 while(j < list.length) { list.data[i++] = list.data[j++]; } list.length = i; } 复制代码
2.2.3, 5
- 与第4题只差了不是有序表，但3，4题的解法仍然可以用
- 只要把要保存的值放在前面，再扔掉后面的值就可以了
- 不要被答案限制了你的思路❌
- 时间复杂度O(n)，空间复杂度O(1)
void del_st(SqList &list, int s, int t) { if (s >= t || list.length == 0) { cout << "ERROR!" << endl; return; } // 1.要保存的值都放在前面 int k = 0; for (int i = 0; i < list.length; i++) { if (list.data[i] < s || list.data[i] > t) { list.data[k++] = list.data[i]; } } // 2.直接扔掉后面的值 list.length = k; } 复制代码
王道答案的做法非常麻烦，不推荐！
