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 }
知识兔View Code4.从有序的顺序表中删除相同的元素,使得表中每个元素都不同。(满足要求的数放在第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 }
知识兔View Code5.合并两个有序表。
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 }
知识兔View Code7.设计一个将含有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 }
知识兔View Code8.找出两个等长、升序数组中的中位数。中位数:升序排列后为与中间位置的数叫做中位数。(每次取两数组中的中位数比较,等于就是中位数,不等于舍弃不可能存在的区间)
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 }
知识兔View Code9.寻找一个数组中的是否存在主元素,存在输出主元素,不存在输出-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 }
知识兔View Code