2020考研-王道数据结构-线性表-顺序表

淡淡的烟草味﹌ 2022-02-04 10:51 280阅读 0赞

# 注意 #

#### 1. 每道题目以函数的形式给出。 ####

#### 2. 为了提高代码的可读性，STL库中的有的函数不在重复，比如Reverse、Swap、Sort等函数。 ####

#### 3. 语言采用的是C++11标准，所以大家编译调试的需要注意，某些函数C++98的编译器不支持。 ####

#### 4. 关于第一张线性表的题目比较简单，数据结构全部采用数组进行模拟。 ####

# 第八题 #

##### 题目简介： #####

将线性表中的前m个元素与线性表中后 n-m 个元素进行交换。  
例如对于序列 1 2 3 4 5 6 7，将前4个元素与后3个进行交换，则序列变成 5 6 7 1 2 3 4

##### 思路描述 #####

这种题目都有小技巧，如果平时没遇见过，考试的时候多半用了很复杂的逻辑，这样面试官的印象分直接就下来了。  
做法就是，先把前 m 个元素逆置，再把后 n - m 个元素逆置，再把整个序列逆置一遍就可以了。大家最好是手动模拟一遍，就知道这个算法的巧妙之处了。  
整个算法的**时间复杂度是O(n)**

##### 代码 #####

void swap_A(int A[], int m, int n)
    {
        
    	reverse(A, m); // 逆置前m个元素
    	reverse(A + m, n - m); // 逆置后 n - m 个元素
    	reverse(A, m + n); // 整个序列逆置一遍
    	return;
    }

# 第九题 #

##### 题目简介 #####

找到有序表中值为 x 的元素， 如果找到，则与该元素后面的元素进行交换；如果未找到，则插入该元素使序列仍然有序。

##### 思路描述 #####

注意该序列使有序的，所以可以二分查找该元素，**二分查找的复杂度是O(lgn)** 级别的，但是如果没找到的话，还需要把该元素插入，**插入该元素的时间复杂度是O(n)** 级别的。

##### 代码 #####

void find_A(int A[], int &length, int x)
    {
        
    	int l = 0, r = length - 1;
    	// 二分查找， 关于二分算法的学习，可以参考我的二分模板总结的博客
    	while (l < r){
        
    		int mid = (l + r) >> 1;
    		if (A[mid] >= x) r = mid;
    		else l = mid + 1;
    	}
    	// 如果找到该元素
    	if (A[l] == x)
    	{
        
    		if (l + 1 == length) return;
    		swap(A[l], A[l + 1]);
    	}
    	else // 如果未找到该元素
    	{
        
    		A[length] = x;
    		for (int i = length; i > 0; i--)
    		{
        
    			if (A[i] < A[i - 1]){
        
    				swap(A[i], A[i - 1]);
    			}
    			else
    				break;
    		}
    		length++; // 注意要更新线性表的长度
    	}
    }

# 第十题 #

##### 题目简介 #####

将线性表中的前p个元素循环左移p个单位，例如1 2 3 4 5 6 7，循环左移3个单位，则成为4 5 6 7 1 2 3.

##### 思路分析 #####

其实大家不难看出这就是第八题吗，所以话不多说。大家对于算法一定要多思考，多上机，毕竟计算机是个实践科学。

##### 代码 #####

void Ror_left(int A[], int length, int p)
    {
         
     	// 算法过程完全是模拟的第八题
    	reverse(A, p);
    	reverse(A + p, length - p);
    	reverse(A, length);
    }

# 第十一题 #

##### 题目简介 #####

给定两个有序序列，请你设计一个算法找出两个序列的中位数，使时间复杂度和空间复杂度尽可能的低。  
例如 序列1：1 2 3 4 5；序列二 8 9 10 11 12。两个序列的中位数应该是 5.

##### 思路分析 #####

考研的时候，大家不要去死磕复杂度和空间复杂度最优的算法，这样往往得不偿失，就比如这个题目，正常去思考的话，我们可以合成一个有序序列吗，这样的时间复杂度是O(n), 其实也是阔以的。  
下面说一个比较优秀的算法，也就是课本给的一个思路:  
比较两个序列的中位数：**序列A的中位数是mid\_a, 序列B的中位数是 mid\_b，默认升序排列。**

1.  mid\_a == mid\_b，那么mid\_a 和 mid\_b就是序列的中位数，因为这时候mid\_a两边的数字个数相同吗，所以一定是。
2.  mid\_a < mia\_b，那么我们可以确定mid\_a左侧偏小的数，和mid\_b右侧偏大的数肯定不包含中位数，所以我们可以舍去序列A和B的各一半。
3.  mid\_a > mid\_b，和2同理。  
    所以这样，我们每次舍弃一半的数，直至找到，这样做的时间复杂度是O(lgn)级别的，并且空间复杂度是O(1)，需要注意的是，舍弃的时候一定要保证A B舍弃的元素个数相同，否则就不对了。

##### 代码 #####

int find_two_mid(int A[], int lena, int B[], int lenb)
    {
        
    	int la = 0, ra = lena - 1;
    	int lb = 0, rb = lenb - 1;
    	while (la < ra)
    	{
        
    		int mida = la + ra >> 1;
    		int midb = lb + rb >> 1;
    		if (A[mida] == B[midb]) return A[mida];
    		else if (A[mida] > B[midb]){
        
    			ra = mida;
    			lb = (rb - lb + 1) & 1 ? midb : midb + 1; // 这个判断保证舍弃时，两个序列舍弃的个数相同
    		}
    		else {
        
    			la = (ra - la + 1) & 1 ? mida : mida + 1;
    			rb = midb;
    		}
    	}
    
    	return min(A[la], B[lb]);
    }

# 第十二题 #

##### 题目简介 #####

找出序列中的主元素，主元素定义为序列中出现次数超多一半的元素。

##### 思路分析 #####

主元素有个特征，比一半的元素个数还多，假设把主元素看成是正电荷，其他元素看成是负电荷，中和后，整个序列是正电的，而且中和后只剩了主元素。  
所以我们可以先模拟这种配对的思路，挑选出来一个为主元素的可以元素，然后再判断该元素是不是。  
怎么配对里？先把第一个元素作为预选元素，当该元素不能配对了，就换，这样的话，最后留下的元素一定是最可能是主元素的元素。

##### 代码 #####

int find_main_elemtype(int A[], int length)
    {
        
    	if (length == 0) return -1;
    	int value = A[0], cnt = 1;
    	// 挑选出可能是主元素的元素
    	for (int i = 1; i < length; i++){
        
    		if (A[i] == value) cnt++;
    		else {
        
    			if (cnt == 0){
        
    				value = A[i];
    				cnt = 1;
    			}
    			else{
        
    				cnt--;
    			}
    		}
    	}
    	cnt = 0;
    	// 验证元素是不是主元素
    	for (int i = 0; i < length; i++)
    	{
        
    		if (A[i] == value)
    			cnt++;
    	}
    	return cnt >(length >> 1) ? value : -1;
    }

# 第十三题 #

##### 题目简介 #####

找出数组中从未出现的最小正整数。

##### 题目分析 #####

这是典型的空间换时间的一种题目，如果我们不开额外空间的话，我能想到的比较快就做法就是把数组排个序，然后扫一遍，这样最快是O(lgn)。如果我们使用额外O(n)的空间的话，可以把时间复杂度降到O(n)。  
但是开空间的话有个小技巧，平常我们用把数当成数组下标去记录，这样的话，我们需要开O(max(A1, A2, … , An))空间，数组中最大的数个空间，但是这个题目很是巧妙了，比如数组的长度是n，我们只需要开O(n)，的空间，因为数组中从未出现的最小正整数只可能是1 ~ n + 1，这样的话，如果出现了大于n的数，我们根本不需要去记录，没什么意义，这个地方大家一定要仔细去体会。

##### 代码 #####

int find_p13(int A[], int lena)
    {
        
    	int* cnt = new int[lena + 1];
    	// 开一块辅助空间
    	memset(cnt, 0, sizeof(cnt) * (lena + 1));
    	for (int i = 0; i < lena; i++)
    	{
        
    		if (A[i] <= lena && A[i] > 0)
    			cnt[A[i]] = 1;
    	}
    
    	for (int i = 1; i <= lena; i++){
        
    		if (!cnt[i])
    			return i;
    	}
    	return lena + 1;
    }