2.2 线性表的顺序表示
using namespace std;
using ElemType = int;
const int MaxSize = 10010;
struct List
{
ElemType data[MaxSize];
int length = 0;
};
01.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。
bool del_min(List &L, ElemType &min)
{
if (L.length == 0) return false;
min = L.data[0];
index = 0;
for (int i = 1; i < L.length; i++)
{
if (min > L.data[i])
{
min = L.data[i];
index = i;
}
}
L.data[index] = L.data[L.length - 1];
L.length--;
return true;
}
02.设计一个高效算法,将顺序表L的所有元素逆置,要求算法的空间复杂度为O(1)。
void my_reverse(List &L)
{
ElemType tmp;
for (int i = 0; i < L.length / 2; i++)
{
tmp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = tmp;
}
}
03.对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除顺序表中所有值为x的数据元素。
void del_x(List &L, ElemType x)
{
int index = 0;
for (int i = 0; i < L.length; i++)
{
if (L.data[i] != x)
{
L.data[index] = L.data[i];
index++;
}
}
L.length = index;
}
04.从顺序表中删除其值在给定值s和t之间(包含s和t,要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。
bool del_st(List &L, ElemType s, ElemType t)
{
if (s >= t || L.length == 0) return false;
int index = 0;
for (int i = 0; i < L.length; i++)
{
if (L.data[i] < s || L.data[i] > t)
{
L.data[index] = L.data[i];
index++;
}
}
L.length = index;
return true;
}
05.从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
bool my_unique(List &L)
{
if (L.length <= 1) return false; //不需要去重
int index = 0;
for (int i = 1; i < L.length; i++)
{
if (L.data[index] != L.data[i])
{
L.data[++index] = L.data[i];
}
}
L.length = index + 1;
return true; //去重完成
}
拓展:无序表去重,时间复杂度O(n)
思路:使用unordered_set
来记录已经遇到的元素。对于每个元素,尝试将其插入到seen
集合中。insert
方法会返回一个pair,其中第二个元素是一个bool值,指示元素是否成功插入(即之前未出现过)。如果元素是首次出现,就将其复制到数组的前面,并最终更新数组的长度。
#include <unordered_set>
void my_unique(List &L) {
unordered_set<ElemType> seen;
int index = 0; // 用于在原数组中存放去重后的元素
for (int i = 0; i < L.length; ++i) {
// 如果元素是首次出现,则加入到seen中,并更新原数组
if (seen.insert(L.data[i]).second) {
L.data[index++] = L.data[i];
}
}
L.length = index; // 更新数组长度为去重后的长度
}
在C++标准库中,unordered_set
的insert
方法实际上返回一个pair
,其中包括一个迭代器和一个布尔值。这个布尔值表示元素是否被插入到集合中:如果元素已经存在,则布尔值为false
;如果元素不存在于集合中并且被成功插入,则为true
。
insert方法实现原理
unordered_set
内部是通过哈希表实现的。当你尝试插入一个元素时:
- 集合首先计算元素的哈希值,以确定应该将其放入哪个桶(bucket)。
- 然后,它会遍历该桶中的元素列表,检查待插入的元素是否已经存在。
- 如果已经存在(即找到一个元素与待插入元素相等),则不进行插入操作,
insert
方法返回一个包含指向该元素的迭代器和false
的pair
。 - 如果不存在,它会在适当的桶中插入新元素,并返回一个包含指向新插入元素的迭代器和
true
的pair
。
时间复杂度
unordered_set
的insert
操作的平均时间复杂度是(O(1)),即常数时间复杂度。这是因为哈希表允许几乎即时的访问和插入操作,假设哈希函数分布良好,哈希冲突较少。
然而,在最坏的情况下,如果哈希函数产生了很多冲突,导致大多数元素都映射到同一个桶中,那么时间复杂度会退化到(O(n))。这种情况下,insert
操作需要遍历桶中的所有元素来检查待插入的元素是否已经存在。
为了避免这种最坏情况的发生,unordered_set
会在元素数量达到当前容量的负载因子(load factor)时自动增加哈希表的容量,并重新分配所有元素,这个过程称为rehashing。这有助于保持元素在桶之间的均匀分布,从而保持操作的平均时间复杂度为(O(1))。
06.将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表。
算法就是归并排序的归并过程。
List merge(List &a, List &b)
{
List res;
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a.data[i] <= b.data[j]) res.data[k++] = a.data[i++];
else res.data[k++] = b.data[j++];
}
while (i < a.length) res.data[k++] = a.data[i++];
while (j < b.length) res.data[k++] = b.data[j++];
res.length = k;
return res;
}
07.已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3,…, am)和(b1, b2, b3,…, bn)。编写一个函数,将数组中两个顺序表的位置互换,即将(b1, b2, b3,…, bn,)放在(a1, a2, a3,…, am)的前面。
void my_reverse(ElemType A[], int l, int r, int len) //反转数组A中[l, r]部分,len为A数组长度
{
if (l < 0 || l > r || r >= len) return; //输入不合法
while (l < r)
{
swap(A[l], A[r]);
l++, r--;
}
}
void exchange(ElemType A[], int m, int n, int len) //将数组A中[0, m - 1]与[m, m + n - 1]部分互换
{
my_reverse(A, 0, m + n - 1, len); //先整体反转
my_reverse(A, 0, n - 1, len); //反转前n个元素
my_reverse(A, n, m + n - 1, len); //再反转后m个元素
}
08.线性表(a1,a2,…,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法,完成用最少时间在表中查找数值为x的元素,若找到,则将其与后继元素位置相交换,若找不到,则将其插入表中并使表中元素仍递增有序。
二分查找,要注意当未找到时,根据要找的x,区分是在边界的左边还是右边
void insert(List &L, int index, ElemType x) //将元素x插入表L的第index + 1个位置,在此及之后的元素都往后推一格
{
if (index < 0 || index > L.length) return; //插入越界
if (L.length >= MaxSize) return; //表已满
for (int i = L.length; i > index; i--)
{
L.data[i] = L.data[i - 1];
}
L.data[index] = x;
L.length++;
}
void binary_search(List &L, ElemType x)
{
int l = 0, r = L.length - 1, mid;
while (l < r) //二分,查找右边界
{
mid = (l + r) / 2;
if (L.data[mid] >= x) r = mid;
else l = mid + 1;
}
if (L.data[l] == x && l < L.length - 1) //找到,且不是最后一个,则交换
{
swap(L.data[l], L.data[l + 1]);
}
else if (L.data[l] == x && l == L.length - 1) //找到,且是最后一个,不交换
return;
else if (L.data[l] > x) //没找到,找到的右边界L.data[l]的值大于x,则插入L.data[l]的左边
{
insert(L, l, x);
}
else if (L.data[l] < x) //没找到,找到的右边界L.data[l]的值小于x,则插入L.data[l]的右边
{
insert(L, l + 1, x);
}
}
09.给定三个序列A、B、C,长度均为n,且均为无重复元素的递增序列,请设计一个时间上尽可能高效的算法,逐行输出同时存在于这三个序列中的所有元素。例如,数组A为{1,2,3],数组B为{2,3,4],数组C为{-1,0,2},则输出2。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
3)说明你的算法的时间复杂度和空间复杂度。
void find_same(ElemType a[], ElemType b[], ElemType c[], int n)
{
int i = 0, j = 0, k = 0;
while (i < n && j < n && k < n)
{
if (a[i] == b[j] && b[j] == c[k])
{
cout << a[i] << '\n';
i++, j++, k++;
}
else
{
int maxn = max(a[i], max(b[j], c[k]));
if (a[i] < maxn) i++;
if (b[j] < maxn) j++;
if (c[k] < maxn) k++;
}
}
}
10.【2010统考真题】设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。
时间复杂度O(n),空间复杂度O(1)
void my_reverse(ElemType A[], int l, int r, int len) //反转数组A中[l, r]部分,len为A数组长度
{
if (l < 0 || l > r || r >= len) return; //输入不合法
while (l < r)
{
swap(A[l], A[r]);
l++, r--;
}
}
void cycle_move(ElemType A[], int p, int n)
{
my_reverse(A, 0, n - 1, n); //反转[0, n - 1]
my_reverse(A, 0, n - p - 1, n); //反转[0, n - p - 1]
my_reverse(A, n - p, n - 1, n); //反转[n - p, n - 1]
}
11.【2011 统考真题】一个长度为L(L≥1)的升序序列S,处在第L/2个位置的数称为S的中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。
代码推广到寻找两个递增序列的第k小的数,令k = L / 2就是寻找中位数
时间复杂度为O(log(L)),空间复杂度为O(1)
int findKth(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k)
{
// 如果数组起始位置超过数组长度,则直接从另一个数组中取第k大的数
if (start1 >= nums1.size()) return nums2[start2 + k - 1];
if (start2 >= nums2.size()) return nums1[start1 + k - 1];
// 如果k等于1,返回两个数组当前起始位置元素的最小值
if (k == 1) return min(nums1[start1], nums2[start2]);
int midVal1 = (start1 + k / 2 - 1 < nums1.size()) ? nums1[start1 + k / 2 - 1] : INT_MAX;
int midVal2 = (start2 + k / 2 - 1 < nums2.size()) ? nums2[start2 + k / 2 - 1] : INT_MAX;
// 递归地调整起始位置和k的值
if (midVal1 < midVal2)
{
return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
}
else
{
return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
}
}
12.【2013统考真题】
int majority(int a[], int n)
{
int cnt = 1, num = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] == num)
{
cnt++;
}
else
{
cnt--;
if (cnt == 0) //cnt减到0,则换一个元素
{
num = a[i];
cnt++;
}
}
}
if (cnt > 0)
{
cnt = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == num) cnt++;
}
}
if (cnt > n / 2) return num;
else return -1;
}
13.【2018统考真题】
开一个额外数组b,记录a数组里出现过的数,最后再遍历b数组,寻找第一个值为0的元素的下标。
额外数组只需要开n + 2个(b[0]不用),因为最差情况就是a数组里出现了1~n的所有自然数,那么最小未出现的正整数就是n + 1,b数组里能遍历到b[n + 1] = 0就行了
时间复杂度O(n),空间复杂度O(n)
int min_pos(int a[], int n)
{
int *b;
b = (int *)malloc(sizeof(int) * n + 2);
for (int i = 0; i < n; i++)
{
if (a[i] < 1 || a[i] > n + 1) continue;
else b[a[i]]++;
}
for (int i = 1; i <= n + 1; i++)
{
if (b[i] == 0) return i;
}
}
错误做法:
int min_pos(int a[], int n)
{
int num = 1;
for (int i = 0; i < n; i++)
{
if (num == a[i]) num++;
}
return num;
}
输入:”3 2 3 1”
输出:”2”
错因:如果较小的数字出现在序列后段,那么无法正确更新未出现过的最小正整数