1.长度为n的顺序表中，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，用于删除线性表中所有值为x的数据元素。（满足要求的数放在第k位上）
1 #include <cstdio> 2 3 /*输出数组名为a、长度为n的数组*/ 4 void print(int *a, int n){ 5 for(int i = 0;i < n; i++){ 6 printf("%d ", a[i]); 7 } 8 puts(""); 9 } 10 11 /*解法1，第几个不等于x的数就应该在结果的第几个位置上,千万记得最后修改删除后的数组长度为k*/ 12 void f1(int *a, int n, int x){ 13 int k = 0; 14 for(int i = 0; i < n; i++){ 15 if(a[i] != x){ 16 a[k++] = a[i]; 17 } 18 } 19 n = k; 20 print(a,k); 21 } 22 23 /*解法2，用k记录等于x的个数，那么下一个不等于x的数在结果中的位置应该提前k个位置，最后数组的长度减去k*/ 24 void f2(int *a, int n, int x){ 25 int k = 0; 26 for(int i = 0; i < n; i++){ 27 if(a[i] == x) 28 k++; 29 else 30 a[i - k] = a[i]; 31 } 32 n -= k; 33 print(a, n); 34 } 35 36 int main() 37 { 38 int a[10] = {1,2,3,2,4,2,5,2,6,2}; 39 f1(a,10,2); 40 41 int b[10] = {1,2,3,2,4,2,5,2,6,2}; 42 f2(b,10,2); 43 return 0; 44 }
2.从有序顺序表中删除其值在给定值s与t之间（包括s和t，要求s<t）的所有元素，如果s或者t不合理或者顺序表为空则显示出错信息并退出运行。（掐掉中间这段）
1 #include <cstdio> 2 3 /*在有序顺序表中，删除值在[s,t]内的元素 4 只需找到第一个大于或者等于s的位置计数为i，然后往后找第一个大于t的数，将其后的所有元素依次放到i及之后*/ 5 6 bool Del_s_t(int a[], int n, int s,int t){ 7 if(s>=t || n == 0) 8 return false; 9 int i = 0, j = 0; 10 for(i = 0; i < n && a[i] < s; i++); 11 if(i >= n) 12 return false;//全部小于s 13 for(j = i; j < n && a[j] <= t; j++); 14 for(;j < n; j++){ 15 a[i++] = a[j]; 16 } 17 n = i; 18 //输出 19 for(int i = 0; i < n; i++){ 20 printf("%d ", a[i]); 21 } 22 puts(""); 23 return true; 24 } 25 int main() 26 { 27 int a[]={2,4,5,6,7,8,9,11,12,13,14,15,15}; 28 Del_s_t(a, 13, 3, 10); 29 return 0; 30 }
3.从顺序表中删除其值在给定值s与t之间（包括s和t，要求s<t）的所有元素，如果s或者t不合理或者顺序表为空则显示出错信息并退出运行(注意与上题的区别是无序的)。
（满足要求的数放在第k位上）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 void print(int a[], int n){ 6 for(int i = 0; i < n; i++){ 7 printf("%d ", a[i]); 8 } 9 puts(""); 10 } 11 /*对于无序的顺序表，将数分成两类，一个在区间一个不在区间，然后计数不在区间的数为k 12 碰到在区间的数应该在结果的第k个位置上，最后总长度为k*/ 13 void Del_s_t2(int a[], int n, int s, int t){ 14 if(s >= t || n == 0) 15 return; 16 int k = 0; 17 for(int i = 0; i < n; i++) { 18 if(a[i] < s || a[i] > t) 19 a[k++] = a[i]; 20 } 21 n = k; 22 print(a, n); 23 } 24 int main() 25 { 26 int a[] = {7,2,9,4, 5,1,3,14}; 27 //sort(a, a + 8); 28 print(a, 8); 29 Del_s_t2(a, 8, 3, 7); 30 return 0; 31 }
4.从有序的顺序表中删除相同的元素，使得表中每个元素都不同。（满足要求的数放在第k位上）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 void print(int a[], int n){ 6 for(int i = 0; i < n; i++){ 7 printf("%d ", a[i]); 8 } 9 puts(""); 10 } 11 /*从有序表中删除相同的元素，只需将于之前不同的数放在第k个位置上即可*/ 12 void Del_diffe(int a[], int n){ 13 int k = 1; 14 for(int i = 1; i < n; i++){ 15 if(a[i] != a[i - 1]) 16 a[k++] = a[i]; 17 } 18 n = k; 19 print(a, k); 20 } 21 int main() 22 { 23 int a[] = {1,1,2,2,2,4,4,5,5,5,5,6,6}; 24 Del_diffe(a, 13); 25 return 0; 26 }
5.合并两个有序表。
1 #include <cstdio> 2 /*合并两个有序表，依次比较，然后添加剩余*/ 3 const int lmax = 50; 4 int c[lmax]; 5 bool merge(int a[], int la, int b[], int lb){ 6 if(la + lb >= lmax) 7 return false; 8 int i = 0,j = 0,k = 0; 9 while(i < la && j < lb){ 10 if(a[i] <= b[j]) 11 c[k++] = a[i++]; 12 else 13 c[k++] = b[j++]; 14 } 15 while(i < la){ 16 c[k++] = a[i++]; 17 } 18 while(j < lb){ 19 c[k++] = b[i++]; 20 } 21 return true; 22 23 for(i = 0; i < k; i++){ 24 printf("%d ", c[i]); 25 } 26 puts(""); 27 } 28 29 int main() 30 { 31 int a[]={1,5,6,8,9,11,12,15,17},la = 9; 32 int b[]={2,3,4,6,7,9,10}, lb = 7; 33 merge(a,la,b,lb); 34 return 0; 35 }
6.将一个顺序表中的两个顺序表互换位置。（矩阵逆置）
#include <cstdio> void print(int a[], int n){ for(int i = 0; i < n; i++){ printf("%d ", a[i]); } puts(""); } /*逆置数组某一区间的方法 数组及其长度，逆置的起始位置和终止位置 中间位置等于起始位置加上终止位置除以2 */ void Reverse(int a[],int n, int s, int t) { if(s >= t || t >= n) return; int mid = (s + t)/2; for(int i = 0; i <= (mid - s); i++){ int temp = a[s + i]; a[s + i] = a[t - i]; a[t - i] = temp; } } /* sc表示交换次数 */ void Reverse2(int a[], int n, int s, int t){ if(s >= t || t >= n) return; int sc = (t - s + 1)/2; for(int i = 0; i < sc;i ++){ int temp = a[s + i]; a[s + i] = a[t - i]; a[t - i] = temp; } } int main() { int a[] = {1,2,3,4, 5,6,7,8}; print(a, 8); Reverse2(a, 8, 0, 7); Reverse2(a, 8, 0, 3); Reverse2(a, 8, 4, 7); print(a, 8); return 0; }
6.用最少的时间在有序表中查找数值为x的元素。（折半查找法）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 void print(int a[], int n){ 6 for(int i = 0; i < n; i++){ 7 printf("%d ", a[i]); 8 } 9 puts(""); 10 } 11 /*折半查找法，选定上界和下届，分三种情况，找到，大了，往左半边找，小了，往右半边找*/ 12 bool B_Search(int a[], int n, int x){ 13 int l = 0, h = n - 1, mid;//low 和 high 分别是顺序表的上界和下届 14 int flag = 0; 15 while(l <= h){ 16 mid = (l + h) / 2; 17 if(a[mid] == x) { 18 flag = 1; 19 break; 20 } 21 if(a[mid] < x) l = mid + 1; 22 else h = mid - 1; 23 } 24 //如果查找失败，插入x到此前h + 1的位置上，因为 25 if(l > h){ 26 int i; 27 for(i = n - 1; i > h; i--) 28 a[i + 1] = a[i]; 29 a[i + 1] = x; 30 } 31 if(flag == 1) 32 return true; 33 return false; 34 } 35 int main() 36 { 37 int a[] = {1,2,3,4,5,6,7}; 38 B_Search(a, 7, 2); 39 print(a, 7); 40 return 0; 41 }
7.设计一个将含有n（n>=1）整数的数组实现循环左移的算法，要求时间和空间复杂度尽可能的高效。（借助矩阵逆运算）
1 #include <cstdio> 2 3 void print(int a[], int n){ 4 for(int i = 0; i < n; i++){ 5 printf("%d ", a[i]); 6 } 7 puts(""); 8 } 9 void Reverse(int a[], int from, int to){ 10 int sc = (to - from + 1) / 2; 11 for(int i = 0; i < sc; i++) { 12 int temp = a[from + i]; 13 a[from + i] = a[to - i]; 14 a[to - i] = temp; 15 } 16 } 17 /*借助矩阵逆运算，ab->ba,即ab->a逆b->a逆b逆->(a逆b逆)逆=ba*/ 18 void Rotate_left(int a[], int n, int p){ 19 Reverse(a, 0, p - 1); 20 Reverse(a, p, n - 1); 21 Reverse(a, 0, n - 1); 22 } 23 24 int main() 25 { 26 int a[] = {1,2,3,4,5,6,7,8,9}; 27 for(int i = 1; i <= 9; i++){ 28 Rotate_left(a, 9, i); 29 print(a, 9); 30 } 31 return 0; 32 }
8.找出两个等长、升序数组中的中位数。中位数：升序排列后为与中间位置的数叫做中位数。（每次取两数组中的中位数比较，等于就是中位数，不等于舍弃不可能存在的区间）
1 #include <cstdio> 2 /*有种折半查找的意味，每次去两个中位数，相等就说明一样， 3 大于或者小于表示中位数在各自区域的另一半，不同的是 4 每次舍弃时要舍弃一样的长度，需要分情况讨论。 5 */ 6 int slove(int a[], int b[], int n){ 7 int s1 = 0,d1 = n - 1,m1, s2 = 0, d2 = n - 1, m2; 8 while(s1 != d1 || s2 != d2){//知道两个数组都遍历完 9 m1 = (s1 + d1) / 2; 10 m2 = (s2 + d2) / 2; 11 if(a[m1] == b[m2]) 12 return a[m1]; 13 if(a[m1] < b[m2]){ 14 if((s1 + d1) % 2 == 0)//若a的元素的个数为奇数个 15 { 16 s1 = m1;//舍弃a中间点之前的部分且保留中间结点 17 d2 = m2;//舍弃b中间点之后的部分且保留中间结点 18 } 19 else//若a的元素的个数为偶数个 20 { 21 s1 = m1 + 1;//舍弃a中间点以及中间点之前的部分 22 d2 = m2; 23 } 24 } 25 else{ 26 if((s2 + d2) % 2 == 0)//若b的元素的个数为奇数个 27 { 28 d1 = m1;//舍弃b中间点之后的部分且保留中间结点 29 s2 = m2;//舍弃a中间点之前的部分且保留中间结点 30 } 31 else//若b的元素的个数为偶数个 32 { 33 d1 = m1; 34 s2 = m2 + 1;//舍弃b中间点以及中间点之前的部分 35 } 36 } 37 } 38 return a[s1] < b[s2] ? a[s1] : a[s2];//返回较小的那个数为中位数 39 } 40 int main() 41 { 42 int a[] = {1,3,5,7,9,11}; 43 int b[] = {0,2,4,6,8,10}; 44 int mid = slove(a, b, 6); 45 printf("%d\n", mid); 46 return 0; 47 }
9.寻找一个数组中的是否存在主元素，存在输出主元素，不存在输出-1。（排序后遍历找出个数最大，最后判断即可）
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 //先排序后将等值元素集中在一起，然后集中遍历，记录个数最多的元素最后判断即可 6 int slove(int a[], int n){ 7 sort(a, a + n); 8 int rs = a[0], max = 1; 9 int temp = 1; 10 for(int i = 1; i < n; i++){ 11 if(a[i] == a[i - 1]) 12 temp++; 13 else{ 14 if(temp > max){ 15 rs = a[i - 1]; 16 max = temp; 17 } 18 temp = 1; 19 } 20 } 21 if(max > n/2) 22 return rs; 23 return -1; 24 } 25 int main() 26 { 27 int i, c, cnt = 1; 28 int a[] = {1, 2, 2, 2, 4, 2,}; 29 printf("%d\n", slove(a, 6)); 30 int b[] = {1, 2, 3, 4, 5, 6,}; 31 printf("%d\n", slove(b, 6)); 32 return 0; 33 }