顺序表经典大题

删除顺序表中的最小值

image-20230718122418457

核心思想

遍历表，查找最小值，并记住位置

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool Del_Min(SqList & list, int & value){
	// 表空
	if(list.length == 0) return false;
	
	// 假定最小值是第1个元素
	value = list.data[0];
	int pos = 0;
	
	// 遍历表，尝试找到更小的元素（从第2个元素开始找起）
	for(int i = 1; i < list.length; i++){
		if(list.data[i] < value){
			value = list.data[i];
			pos = i;
		}
	}
	
	// 题目要求：空出的位置由最后一个元素顶替
	list.data[pos] = list.data[list.length - 1];
	
	list.length--; // 这一步是最最最容易忘记的！！！
	
	return true;
}

逆置顺序表

image-20230718124559870

核心思想

算法板子…

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Reverse(SqList & list, int from, int to){
	// 空表
	if(list.length == 0) return false;

    // 输入非法
    if(from >= to) return false;
    
    // 向上取整
	int mid = (to - from + 1) / 2;
	
	for(int i = 0; i < mid; i++){
		int temp = list.data[from + i];
		list.data[from + i] = list.data[to - i];
		list.data[to - i] = temp;
	}
	
	return true;
}

顺序表批量删除指定值 x 元素

image-20230718125544632

核心思想

利用变量k，从0开始，遍历表，只保留非 x 元素

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Del_x(SqList & list, int x){
	// 空表
	if(list.length == 0) return false;
	
	int k = 0;
	for(int i = 0; i < list.length; i++)
		if(list.data[i] != x)
			list.data[k++] = list.data[i];
	
	// k 才是有效表长
	list.length = k;
	
	return true;
}

顺序表在某条件下的批量删除

image-20230718134328974

核心思想

算法板子…

image-20230718135751532

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool Del_range(SqList & list, int s, int t){
	// 空表
	if(list.length == 0) return false;
	
	// 题目要求，非法输入判定
	if(s >= t) return false;
	
	int i = 0, k = 0;
	
	while(i < list.length){
		// 值在[s,t]这个范围内 k++
		if(list.data[i] >= s && list.data[i] <= t) k++;
		else list.data[i - k] = list.data[i]; // 不在这个范围则直接位移
		i++;
	}
	
	// 更新表长，删除了 k 个
	list.length -= k;
	
	return true;
}

删除顺序表中重复元素

image-20230718140838298

核心思想

经典的双指针算法。

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Del_repeat(SqList & list){
	// 空表
	if(list.length == 0) return false;
	
	int i,j;
	
	for(i = 0, j = 1; j < list.length; j++)
		// 出现不同元素
		if(list.data[i] != list.data[j])
			// 前移 不能写 i++ 必须要写 ++i ！！！！
             // 不同的元素要放在 i 的下一个位置(保证)
			list.data[++i] = list.data[j];
		
	
	list.length = i + 1;
	
	return true;
}

线性表的 AB => BA 问题

image-20230718143153144

核心思想

image-20230718145427110

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool Reverse(SqList & list, int from, int to){
	// 空表
	if(list.length == 0) return false;
	
	// 输入非法
	if(from >= to) return false;
	
	// 向上取整
	int mid = (to - from + 1) / 2;
	
	for(int i = 0; i < mid; i++){
		int temp = list.data[from + i];
		list.data[from + i] = list.data[to - i];
		list.data[to - i] = temp;
	}
	
	return true;
}

void Converse(SqList & list, int m, int n){
	Reverse(list, 0, m + n - 1);
	Reverse(list, 0, n - 1);
	Reverse(list, n, m + n - 1);
}

顺序表的二分查找

image-20230718145821268

核心思想

使用折半查找。

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void SearchExchangeInsert(SqList & list, int x){
	// 二分
	int left = 0, right = list.length - 1, mid;
	
	while(left <= right){
		// 防溢出
		mid = left + (right - left) / 2;
		
		if(list.data[mid] == x) break;
		else if(list.data[mid] < x) left = mid + 1;
		else right = mid - 1;
	}
	
	// 找到了，与它后面那个元素进行交换（要有的话）
	if(list.data[mid] == x && mid != list.length - 1){
		swap(list.data[mid],list.data[mid + 1]); // 偷懒了
	}
	
	// 没找到
	if(left > right){
		int i;
		for(i = list.length - 1; i > right; i--){
			list.data[i + 1] = list.data[i];
		}
		list.data[i + 1] = x;
	}
}

顺序表的主元（摩尔投票法）

题目太长了，就不给了。

大概意思是主元的数量大于总数量的一半

核心思想

算法板子…

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int MoreThanHalfNum_Solution(SqList list){
	int cnt = 0;
	int val;
	
	for(int i = 0; i < list.length; i++){
		if(!cnt) val = list.data[i], cnt++;
		else if(val == list.data[i]) cnt++;
		else cnt--;
	}
	
	// 如果有主元。统计出主元实际出现次数
	if(cnt > 0){
		for(int i = cnt = 0; i < list.length; i++)
			if(list.data[i] == val) cnt++;
	}
	
	// 主元超过总元素长度的一半
	if(cnt > list.length / 2) return val;
	else return -1; // 不存在主元
}

顺序表中未出现的最小正整数

image-20230718163359493

核心思想

桶计数

核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int FindMissMin(SqList list){
	int i;
	
	int * B; // 桶
	B = (int *)malloc(sizeof(int) * list.length);
	memset(B, 0, sizeof(int) * list.length); // 赋初始值为0
	
	// 计数
	for(i = 0; i < list.length; i++)
		// 合法的范围
		if(list.data[i] > 0 && list.data[i] <= list.length)
			B[list.data[i] - 1] = 1; // 标记出现过
	// 从桶里面找最小整数
	for(i = 0; i < list.length; i++)
		if(!B[i]) break;
	
	return i + 1;
	
}