顺序表结构体
考试直接使用，一般不会让你写出结构体
#define MaxSize 50 typedef struct { ElemType data[MaxSize]; int length; }SqList; 复制代码
2.2.3, 1
- 暴力解法一般就是循环，循环一次不行，就来两次，两次不行三次 ...
- 时间复杂度 O(n)，空间复杂度O(1)
int del_min(SqList &list) { if (list.length == 0) { cout << "Error!" << endl; return -1; } // 1.假设0号元素最小 int min = list.data[0]; int pos = 0; // 2.循环找出最小元素并记录位置, 从1开始 for (int i = 1; i < list.length; i++) { if (list.data[i] < min) { min = list.data[i]; pos = i; } } // 3.删除最小元素并用最后一个元素替换 list.data[pos] = list.data[list.length - 1]; list.length--; return min; } 复制代码
2.2.3, 2
- 暴力就是再整一个数组，原数组从末尾循环遍历放到新数组里
- 要求空间复杂度O(1)的话，从头循环到中间，交换头尾元素
- 偶数或者奇数个元素，循环到中间，都是
< length/2，因为如果长度为4或者5，都是循环到下标为1即停，为5的时候最中间的元素（下标为2）不需要移动。 - 时间复杂度O(n)，空间复杂度O(1)
void reverse(SqList &list) { for (int i = 0; i < list.length / 2; i++) { // 不让用swap()的话，可以定义一个辅助变量来交换 swap(list.data[i], list.data[list.length - 1 - i]); } } 复制代码
2.2.3, 3
- 暴力就是再整一个数组，循环遍历把不等于x的元素都放入新数组
- 时间复杂度O(n)，空间复杂度O(1)就要求一次循环内解决
- 把所有等于x的元素都扔到最后，然后 length 减掉就可以了
- 反向：也就是把所有不等于x的元素扔到前面，后面自然就是等于x的元素了
void del_x(SqList &list, int x) { int k = 0; for (int i = 0 ; i < list.length ; i++) { // 1.把所有要保存的值都放在前面 if (list.data[i] != x) { list.data[k++] = list.data[i]; } } // 2.直接扔掉后面的元素 list.length = k; } 复制代码
- 一次循环 -> 双指针
- 类似快排，从两端向中间移动，将左边的x与右边的非x交换
// 太麻烦了，不如上一个方法 void del_x_2(SqList &list, int x) { int i = -1, j = list.length, k = 0; while (i < j) { while (list.data[++i] != x); while (list.data[--j] == x) k++; if (i < j) { swap(list.data[i], list.data[j]); k++; } } list.length -= k; }
