参考教材: 《2021年王道数据结构复习指导》
$2.2$ 顺序表
- 采用$C$++$11$完成习题
- 一般情况下,顺序表的数据类型采用$\textrm{int}$
- $\textrm{print(int *a,int n)}$函数用于打印顺序表
- $\textrm{swap(type &a,type &b)}$函数用于交换两个元素的值
- 测试结果将写在注释部分
- 源代码下载
$0$.程序框架
#include <iostream> using namespace std; void print(int *a,int n) { for(int i = 0;i < n;i++) cout<<a[i]<<(i==n-1?"\n":" "); } /* * 镶嵌函数和测试代码 */ int main(void) { //test_chapter2_array_1(); //test_chapter2_array_2(); //test_chapter2_array_3(); //test_chapter2_array_4(); //test_chapter2_array_5(); //test_chapter2_array_6(); //test_chapter2_array_7(); //test_chapter2_array_8(); //test_chapter2_array_9(); //test_chapter2_array_10(); //test_chapter2_array_11(); //test_chapter2_array_12(); //test_chapter2_array_13(); return 0; }
$1$. 删除顺序表中的最小元素(假设唯一)并返回该元素,将后续元素前移来填充该空位,若表空则报错并退出。
bool problem_chapter2_array_1(int *a,int &size,int &val) { if(size == 0) return false; int min_index = 0; for(int i = 1;i < size;i++) if(a[i] < a[min_index]) min_index = i; val = a[min_index]; for(int i = min_index;i < size-1;i++) a[i] = a[i+1]; size--; return true; } void test_chapter2_array_1() { int a[8] = {8,2,6,5,1,4,3,9}; int size = 8; int val; print(a,size); if(problem_chapter2_array_1(a,size,val)) { cout<<"min value:"<<val<<endl; print(a,size); } } /* * Test Chapter2 Array 1 Result: * 8 2 6 5 1 4 3 9 * min value:1 * 8 2 6 5 4 3 9 */
$2$.设计一个高效算法逆置顺序表内的所有元素,要求空间复杂度为$O(1)$。
void problem_chapter2_array_2(int *a,int size) { for(int i = 0;i < (size>>1);i++) swap(a[i],a[size-i-1]); } void test_chapter2_array_2() { int a[8] = {1,2,3,4,5,6,7,8}; int size = 8; print(a,size); problem_chapter2_array_2(a,size); print(a,size); } /* * Test Chapter2 Array 2 Result: * 1 2 3 4 5 6 7 8 * 8 7 6 5 4 3 2 1 */
$3$.对长度为$n$的顺序表,编写一个时间复杂度度为$O(n)$,空间复杂度为$O(1)$的算法,删除线性表中所有值为$x$的元素。
void problem_chapter2_array_3(int *a,int &n,int x) { int index = 0; for(int i = 0;i < n;i++) if(a[i] != x) a[index++] = a[i]; n = index; } void test_chapter2_array_3() { int a[9] = {1,2,1,3,1,4,1,1,5}; int size = 9; print(a,size); problem_chapter2_array_3(a,size,1); print(a,size); } /* * Test Chapter2 Array 3 Result: * 1 2 1 3 1 4 1 1 5 * 2 3 4 5 */
$4$.从有序顺序表中删除在给定$s$和$t$之间的所有元素(包括$s,t$),如果$s,t$不合理或者表空,则报错并退出。
bool problem_chapter2_array_4(int *a,int &n,int s,int t) { if(s >= t || !n) return false; int index = 0; for(int i = 0;i < n;i++) if(a[i] < s || a[i] > t) a[index++] = a[i]; n = index; } void test_chapter2_array_4() { int a[9] = {1,2,3,4,5,6,7,8,9}; int size = 9; print(a,size); problem_chapter2_array_4(a,size,3,6); print(a,size); } /* * Test Chapter2 Array 4 Result: * 1 2 3 4 5 6 7 8 9 * 1 2 7 8 9 */
$5$.从顺序表(和4相比,不再有序)中删除在给定$s$和$t$之间的所有元素(包括$s,t$),如果$s,t$不合理或者表空,则报错并退出。
bool problem_chapter2_array_5(int *a,int &n,int s,int t) { if(s >= t || !n) return false; int index = 0; for(int i = 0;i < n;i++) if(a[i] < s || a[i] > t) a[index++] = a[i]; n = index; } void test_chapter2_array_5() { int a[9] = {3,1,5,7,9,2,4,6,8}; int size = 9; print(a,size); problem_chapter2_array_5(a,size,3,6); print(a,size); } /* * Test Chapter2 Array 5 Result: * 3 1 5 7 9 2 4 6 8 * 1 7 9 2 8 */
$6$.从有序顺序表中删除所有其值重复的元素,使表中的所有元素的值均不同。
void problem_chapter2_array_6(int *a,int &size) { int index = 1; for(int i = 1;i < size;i++) if(a[i] != a[i-1]) a[index++] = a[i]; size = index; } void test_chapter2_array_6() { int a[10] = {1,2,2,3,3,3,4,4,4,4}; int size = 10; print(a,size); problem_chapter2_array_6(a,size); print(a,size); } /* * Test Chapter2 Array 6 Result: * 1 2 2 3 3 3 4 4 4 4 * 1 2 3 4 */
$7$.将两个有序顺序表合并成一个新的有序表,并由函数返回结果顺序表。
int* problem_chapter2_array_7(int *a,int n,int *b,int m,int& size) { size = n+m; int *c = new int [size]; int i = 0,j = 0,k = 0; while(i < n && j < m) { if(b[j] < a[i]) c[k++] = b[j++]; else c[k++] = a[i++]; } while(i < n) c[k++] = a[i++]; while(j < m) c[k++] = b[j++]; return c; } void test_chapter2_array_7() { int a[] = {1,3,5,7,9}; int b[] = {2,4,6,8}; int size = 0; int *c = problem_chapter2_array_7(a,5,b,4,size); print(c,size); } /* * Test Chapter2 Array 7 Result: * 1 2 3 4 5 6 7 8 9 */
$8$.已知在一维数组中$A[m+n]$中依次存放两个线性表$(a_1,a_2,a_3, …… ,a_m)$和$(b_1,b_2,b_3, …… ,b_n)$,试编写一个函数,将数组中两个顺序表的位置互换,变为$(b_1,b_2,b_3, …… ,b_n)$和$(a_1,a_2,a_3, …… ,a_m)$。
void reverse(int *a,int begin,int end) { for(int i = begin;i < (end+begin)/2;i++) swap(a[i],a[end+begin-i-1]); } void problem_chapter2_array_8(int *a,int m,int n) { reverse(a,0,m+n); reverse(a,0,n); reverse(a,n,m+n); } void test_chapter2_array_8() { int a[10] = {1,2,3,4,1,2,3,4,5,6}; int size = 10; print(a,size); problem_chapter2_array_8(a,4,6); print(a,size); } /* * Test Chapter2 Array 8 Result: * 1 2 3 4 1 2 3 4 5 6 * 1 2 3 4 5 6 1 2 3 4 */
$9$.在有序顺序表内查找值为$x$的元素,并将其与其后继元素交换,若找不到则将其插入表中使表仍然有序。
void problem_chapter2_array_9(int *a,int &size,int x) { int left = 0,right = size-1,mid; while(left <= right) { mid = (left+right)>>1; if(a[mid] < x) left = mid+1; else if(a[mid] > x)right = mid-1; else break; } if(a[mid] == x && mid != size-1) swap(a[mid],a[mid+1]); else if(left > right) { for(int i = size-1;i > right;i--) a[i+1] = a[i]; a[right+1] = x; size++; } } void test_chapter2_array_9() { int a[10] = {1,2,3,4,6,7,8,9}; int size = 8; print(a,size); problem_chapter2_array_9(a,size,5); //problem_chapter2_array_9(a,size,7); print(a,size); } /* * Test Chapter2 Array 9 Result: * 1 2 3 4 6 7 8 9 * x = 5 * 1 2 3 4 5 6 8 7 9 * 1 2 3 4 6 7 8 9 * x = 7 * 1 2 3 4 6 8 7 9 */
$10$.数组$a$中存放有$n$个元素,设计一个时间和空间两方面都尽可能高效的算法,将$a$中保存的序列循环左移$p(0<p<n)$个位置,即把$(a_0,a_1,a_2, …… ,a_{n-1})$变换为$(a_p,a_{p+1},……,a_{n-1},a_0,a_1, …… ,a_{p-1})$,说明你设计的时间复杂度和空间复杂度。
//调用第8题撰写的reverse函数 void problem_chapter2_array_10(int *a,int size,int p) { reverse(a,0,size); reverse(a,0,size-p); reverse(a,size-p,size); } void test_chapter2_array_10() { int a[10] = {1,2,3,4,1,2,3,4,5,6}; int size = 10; print(a,size); problem_chapter2_array_10(a,10,4); print(a,size); } /* * Test Chapter2 Array 10 Result: * 1 2 3 4 1 2 3 4 5 6 * 1 2 3 4 5 6 1 2 3 4 */
时间复杂度: $O(n)$
空间复杂度: $O(1)$
$11$.定义中位数是第$\textrm{(int)n/2}$个元素,现给出两个等长有序的数组,找出他们合并的中位数,说明你设计的时间复杂度和空间复杂度。
int problem_chapter2_array_11(int *a,int *b,int n) { int left1 = 0,right1 = n-1,left2 = 0,right2 = n-1,mid1,mid2; while(left1 != right1 || left2 != right2) { mid1 = (left1+right1)/2; mid2 = (left2+right2)/2; if(a[mid1] == b[mid2]) return a[mid1]; if(a[mid1] < b[mid2]) { if(!((left1+right1)&1)) { left1 = mid1; right2 = mid2; } else { left1 = mid1+1; right2 = mid2; } } else { if(!((left2+right2)&1)) { right1 = mid1; left2 = mid2; } else { right1 = mid1; left2 = mid2+1; } } } return a[left1] < b[left2]?a[left1]:b[left2]; } void test_chapter2_array_11() { int a[5] = {11,13,15,17,19}; int b[5] = {2,4,6,8,20}; int n = 5; cout<<problem_chapter2_array_11(a,b,5)<<endl; } /* * Test Chapter2 Array 11 Result: * 11 */
时间复杂度: $O(\log_2n)$
空间复杂度: $O(1)$
$12$.定义主元素:存在个数超过数组长度一半的元素,搜索一个数组是否存在主元素,是则返回该元素,否则返回-$\textrm{1}$。
本题采用了$BM$投票算法,详情可以参考文章$\textrm{Boyer-Moore}$投票算法
int problem_chapter2_array_12(int *a,int size) { int val = -1; int count = 0; for (int i = 0;i < size;i++) { if (a[i] == val) count++; else { count--; if(count < 0) { val = a[i]; count = 1; } } } return (count>0)?val:-1; } void test_chapter2_array_12() { int a[8] = {0,5,5,3,5,7,5,5}; int b[8] = {0,5,5,3,5,1,5,7}; cout<<problem_chapter2_array_12(a,8)<<endl; cout<<problem_chapter2_array_12(b,8)<<endl; } /* * Test Chapter2 Array 12 Result: * 5 * -1 */
时间复杂度: $O(n)$
空间复杂度: $O(1)$
$13$.寻找一个数组没出现的最小正数,例如$\{-5,3,2,3\}$返回$1$,$\{1,2,3\}$返回$4$。说明你设计的时间复杂度和空间复杂度。
int problem_chapter2_array_13(int *a,int size) { bool *vis = new bool [size+1](); for(int i = 0;i < size;i++) if(a[i] > 0) vis[a[i]] = true; for(int i = 1;i <= size;i++) if(!vis[i]) return i; return size+1; } void test_chapter2_array_13() { int a[4] = {-5,3,2,3}; int b[3] = {1,2,3}; cout<<problem_chapter2_array_13(a,4)<<endl; cout<<problem_chapter2_array_13(b,3)<<endl; } /* * Test Chapter2 Array 13 Result: * 1 * 4 */
时间复杂度: $O(n)$
空间复杂度: $O(n)$
$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$
$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$
$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$
$\textrm{Last Modified: 2021-04-03 15:30}$
退出登录?