顺序表例题_顺序表习题

1. 基础题

1. 从顺序表中删除具有最小值的元素，并由函数返回被删元素的值，空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行
   算法思想：

1. 输入顺序表的元素值，获得表长
2. 设计函数，定义变量$min$比较出顺序表最小值，并记录序号
3. 将$len-1$的值替换最小元素值，函数返回最小元素

/*从顺序表中删除具有最小值的元素，并由函数返回被删元素的值，
空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行*/

#include<stdio.h>

#define maxsize 10

typedef struct seq_list
{
	/* data */
	int data[maxsize];
	int len;			//输入顺序表元素时，自增，得到长度
}seq_list;

int del_min(seq_list &q)
{
	int min = q.data[0];
	int i ,k = 0;

	for(i=1;i<q.len;i++)
	{
		if(min>q.data[i])
		{
			min = q.data[i];
			k = i;
		}
	}
	q.data[k] = q.data[q.len-1];
	q.len--;
	return min;
}

int main()
{
	seq_list q;
	int res;
	q.len = 0;
	printf("input %d array:\n",maxsize);
	for(int i=0;i<maxsize;i++)
	{
		scanf("%d",&q.data[i]);
		q.len++;		//获得顺序表的长度
		printf("i = %d, len = %d\n",i,q.len);
	}

	res = del_min(q);
	printf("min is: %d\n",res);
	for(int i=0;i<maxsize-1;i++)
	{
		printf("%d ",q.data[i]);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

注：

1. $len$首先要初始化为0；否则会被初始化为任意数
2. $len$需要在初始化顺序表的时候赋值，$len$的值比序号大1，所以最后一个元素为$len-1$

2. 设计一个高效算法，将顺序表工的所有元素逆置，要求算法的空间复杂度为$O(1)$.
   算法思想：

1. 设计函数无返回值，改变顺序表元素即可
2. 定义一个自增变量（$i=0$），一个自减变量（$j=q.len$），$i<j$时交换（$q.data[i],q.data[j]$）

// 2. 设计一个高效算法，将顺序表工的所有元素逆置，要求算法的空间复杂度为O(1).
#include<stdio.h>

#define maxsize 10

typedef struct seqlist
{
    /* data */
    int data[maxsize];
    int len;
}seqlist;

void reverse(seqlist &q)
{
    int temp;
    int j = q.len-1;
    for(int i=0;i<j;i++,j--)
    {
        temp = q.data[i];
        q.data[i] = q.data[j];
        q.data[j] = temp;
    }
}

int main()
{
    seqlist q;
    q.len = 0;
    printf("input %d array:\n",maxsize);
    for(int i=0;i<maxsize;i++)
    {
        scanf("%d",&q.data[i]);
        q.len++;
        printf("i = %d, len = %d\n",i,q.len);
    }
    printf("q.len = %d\n",q.len);

    reverse(q);

    printf("q.len = %d\n",q.len);
    for(int i=0;i<q.len;i++)
    {
        printf("%d ",q.data[i]);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3. 对长度为n的顺序表工，编写一个时间复杂度为$O(n)$、空间复杂度为$O(1)$的算法，该算法删除线性表中所有值为$x$的数据元素。
   算法思路1：

1. 设计函数，定义$k$记录顺序表之前$x$所出现次数
2. 判断当前数是否为$x$，不为时将第$i$个数赋值给第$i-k$,若为$x$，增加$k$，进入下一次循环
3. 更新$q.len$的长度，$q.len=q.len-k$

算法思路2：

1. 设计函数，定义$k$,通过$k$重新对顺序表赋值
2. 若当前数等于$x$, 将$i$加1，$k$不变，进入下一轮，将下一个不等于$x$的值放入$q.data[k]$中

// 3. 对长度为n的顺序表工，编写一个时间复杂度为O（n)、空间复杂度为O（1)的算法，
//该算法删除线性表中所有值为x的数据元素。
#include<stdio.h>

#define maxsize 10

typedef struct seqlist
{
    int data[maxsize];
    int len;
}seqlist;

void del_x1(seqlist &q,int x)//设置K 判断x出现的次数，将i 的值向前移动
{
    printf("x = %d\n",x);
    int k = 0;
    for(int i=0;i<q.len;i++)
    {
        if(q.data[i] != x)//现判断q.data[i]是否为x,不相等则赋值
        {
            q.data[i-k] = q.data[i];
        }
        else k++;// 如果相等，将k + 1 进入下一次循环
    }
    q.len = q.len-k;
}

void del_x2(seqlist &q, int x)//设置k 重新赋值，遇到x i加一，k不变
{
    int k = 0;
    for(int i=0;i<q.len;i++)
    {
        if(q.data[i]!=x)
        {
            q.data[k] = q.data[i];
            k++;
        }
    }
    q.len = k;
}

int main()
{
    seqlist q;
    q.len = 0;
    int x =0;
    printf("input %d array:\n",maxsize);
    for(int i=0;i<maxsize;i++)
    {
        scanf("%d",&q.data[i]);
        q.len++;
    }
    printf("input x:\n");
    scanf("%d",&x);

    del_x2(q,x);

    for(int i=0;i<q.len;i++)
    {
        printf("%d ",q.data[i]);
    }

    return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

注：

1. 思路一中，将第$i$ 的值赋值给 $i-k$,将后面的数，跳过$k$个$x$,移动到前面
2. 得到新的顺序表后，记得修改表长，思路一：减去$k$,思路二：长度等于$k$

4. 从有序顺序表中删除其值在给定值$s$与$t$之间（要求$s<t$）的所有元素，如果$s$或$t$不合理或顺序表为空，则显示出错信息并退出运行。
   算法思路：

1. 找出顺序表中值大于、等于$s$的值，记录位置$i$，以及小于等于$t$的值，记录位置$j$
2. 将$j$位置后的元素挪动到$i$位置之后，更新顺序表表长

// 4. 从有序顺序表中删除其值在给定值s与t之间（要求s<1）的所有元素，如
// 果s或1不合理或顺序表为空，则显示出错信息并退出运行。
#include<stdio.h>

#define maxsize 10

typedef struct seqlist
{
    /* data */
    int data[maxsize];
    int len;
}seqlist;

int del_s_t(seqlist &q, int s,int t)
{
    if(s<0||t>maxsize||s>t)
    {
        printf("s or t error\n");
        return 0;
    }
    int i,j;
    for( i=0;i<q.len&&q.data[i]<s;i++);//同时要判断s是否存在与顺序表中，搜索范围不要超出线性表
    if(i>=q.len) return 0;
    for( j=i;j<q.len&&q.data[j]<t;j++);
    while(j<q.len)
    {
        q.data[i++] = q.data[j++];
    }
    q.len = i;
    return 1;
}

int main()
{
    seqlist q;
    int s,t;
    q.len = 0;
    for(int i=0;i<maxsize;i++)
    {
        q.data[i] = i+1;
        q.len++;
    }
    for(int i=0;i<q.len;i++)
    {
        printf("q.data[%d] = %d\n",i,q.data[i]);
    }
    printf("input s and t:\n");
    scanf("%d",&s);
    scanf("%d",&t);
    del_s_t(q,s,t);

    for(int i=0;i<q.len;i++)
    {
        printf("%d\n",q.data[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

注：

1. 顺序表中寻找位置$i,j$时，同时要判断$s$是否存在与顺序表中，搜索范围不要超出顺序表
2. 挪动完顺序表后，记得更新顺序表表长，表长为$i$的值

5. 从顺序表中删除其值在给定值s与1之间（包含s和1，要求s<1)的所有元素，如果s或1不合理或顺序表为空，则显示出错信息并退出运行。

算法思路：

1. 设置变量$k$ 记录元素值在$st$ 之间的个数
2. 如果第$i$ 的值在$st$之间，增加$k$ 的值，若不在，则将第$i$个元素赋值给第$i-k$的位置
3. 更新顺序表表长

// 5. 从顺序表中删除其值在给定值s与1之间（包含s和1，要求s<1)的所有元
// 素，如果s或1不合理或顺序表为空，则显示出错信息并退出运行。
#include<stdio.h>

#define maxsize 10

typedef struct seqlist
{
    int data [maxsize];
    int len;
}seqlist;

int del_s_t2(seqlist &q,int s,int t)
{
    int k = 0;
    if(s>t||q.len<1)
    {
        printf("s or t error");
        return 0;
    }
    for(int i=0;i<q.len;i++)
    {
        if(q.data[i]<=t&&q.data[i]>=s)
        {
            k++;
        }
        else
        {
            q.data[i-k] = q.data[i];
        }
    }
    q.len = q.len-k;
    return 1;
}

int main()
{
    seqlist q;
    int s,t;
    q.len = 0;
    printf("input %d array:\n",maxsize);
    for(int i=0;i<maxsize;i++)
    {
        scanf("%d",&q.data[i]);
        q.len++;
    }
    printf("input s and t:\n");
    scanf("%d",&s);
    scanf("%d",&t);

    del_s_t2(q,s,t);

    for(int i=0;i<q.len;i++)
    {
        printf("q.data[%d] = %d ",i,q.data[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

6. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
   算法思想：

类似于直接插入排序：因为是有序表，若为无序，则用散列表

1. 定义两个变量，一个指向当前位置$i$，一个指向待判断是否是重复数位置$j$
2. 设置循环（循环判定条件为，$j$ 是否超出$q.len$ ）
3. 若不相等，将$j$指向的值赋值给$i+1$的位置，否则，$j++$,判断下一个数是否重复

// 6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
#include<stdio.h>

#define maxsize 10

typedef struct seqlist
{
    int data[maxsize];
    int len;
}seqlist;

void del(seqlist &q)
{
    int i,j;
    i=0;
    j=1;
    while(j<q.len)
    {
        if(q.data[i]!=q.data[j])
        {
            q.data[++i] = q.data[j];
        }
        j++;
    }
    q.len = i+1;
}

int main()
{
    seqlist q;
    q.len = 0;
    printf("input %d array:\n",maxsize);
    for(int i=0;i<maxsize;i++)
    {
        scanf("%d",&q.data[i]);
        q.len++;
    }
    del(q);
    for(int i=0;i<q.len;i++)
    {
        printf("q.data[%d] = %d \n",i,q.data[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

注：

更新有序表长度时，长度为$i+1$, $i$ 指向倒数第二个数

7. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表.
   算法思想：

1. 主函数中定义三个顺序表，其中两个赋值，另一个为空
2. 函数中定义3个变量，分别指向3个表，在不超出$q1,q2$长度的情况下，将较小的数放入$q$ 表中
3. 分别循环判断$q1,q2$中是否指向最后元素，否则将其拷贝进$q$表中

// 7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表.
#include<stdio.h>

#define maxsize 50

typedef struct seqlist
{
    int data[maxsize];
    int len;
}seqlist;

void merge(seqlist q1, seqlist q2,seqlist &q)
{
    int i = 0,j = 0,k = 0;
    while(i!=q1.len&&j!=q2.len)
    {
        if(q1.data[i]<q2.data[j])
        {
            q.data[k++] = q1.data[i++];
        }
        else q.data[k++] = q2.data[j++];
    }
    while(i<q1.len)   // 此处是while循环，循环遍历剩下的所有元素，不只一个
    {
        q.data[k++] = q1.data[i++];
    }
    while(j<q2.len)
    {
        q.data[k++] = q2.data[j++];
    }
    q.len = k;
    
}

int main()
{
    seqlist q1,q2,q;
    q1 = {2,3,5,7,9,24,26};
    q2 = {4,11,14,16,20};
    q1.len = 7;
    q2.len = 5;
    q.len = 0;

    for(int i=0;i<q1.len;i++)
    {
        printf("q1 = %d \n",q1.data[i]);
    }
    for(int i=0;i<q2.len;i++)
    {
        printf("q2 = %d \n",q2.data[i]);
    }
    merge(q1,q2,q);
    printf("q.len = %d\n",q.len);

    for(int i=0;i<q.len;i++)
    {
        printf("q.data[%d] = %d\n",i,q.data[i]);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

注：

1. 顺序表的赋值操作与数组相似
2. 函数中，判断$q1,q2$ 是否为空时，要用$while$ 因为剩余元素不只为一个，需要循环判断

8. 已知在一维数组$A[m+n]$中依次存放两个线性表$(a_1,a_2,a_3\dots ,a_m)$和$(b_1,b_2,b_3\dots ,b_n)$。试编写一个函数，将数组中两个顺序表的位置互换，即将$(b_1,b_2,b_3\dots ,b_n)$放在$(a_1,a_2,a_3\dots ,a_m)$的前面。

算法思想：

1. 先将$a_1$~ $a_m$逆转，再将$b_1$~ $b_m$逆转，最后将整个数组逆转
2. 设置两个函数，$exchange$用来调用逆转函数，分别调用3次$reverse$用来逆置指定长度的数组

// 已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…,am)和(b1,b2,b3…,bn)。
// 试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3…,bn)放在(a1,a2,a3…,am)的前面。
#include<stdio.h>

void reverse(int a[],int left,int right)
{
    int tmp;
    printf("a[left] = %d,a[right] = %d\n",a[left] ,a[right]);
    while(left<right)
    {
        tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        printf("a[left] = %d,a[right] = %d\n",a[left] ,a[right]);
        left++;
        right--;
    }
}

void exchange(int a[],int m, int n)
{
    reverse(a,0,m-1);
    reverse(a,m,n-1);
    reverse(a,0,n-1);
}

int main()
{
    int a[11] = {11,12,13,14,15,23,24,25,26,27,28};
    exchange(a,5,11);
    for(int i=0;i<11;i++)
    {
        printf("a[%d] = %d\n",i,a[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

9. 线性表$(a_1,a_2,a_3\dots ,a_m)$中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为$x$的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。

线性表有序，折半查找时间最少

1. 折半查找是否存在$x$, 找到时，跳出循环，还需判断$x$是否为最后一个值，若为最后一个值，则不交换元素，原样输出线性表
2. $x$不存在时，从后向前，将元素向后挪一位，将$x$放入$low$的位置，$low$指向插入位置，$high+1$指向插入位置

// 线性表（a1，a2，a…，an）中的元素递增有序且按顺序存储于计算机内。要求设
// 计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后
// 继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。

#include<stdio.h>

#define maxsize 50

typedef struct seqlist
{
    int data[maxsize];
    int len;
}seqlist;

void binary(seqlist &q, int x)
{
    int low = 0;
    int high = q.len-1;
    int mid,tmp;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(q.data[mid]<x)
        {
            low = mid+1;
        }
        else if(q.data[mid]>x)
        {
            high = mid-1;
        }
        else
        {
            break;
        }
    }
    if(q.data[mid]==x&&mid!=q.len-1)//注意特殊情况，当x为最后一个值，不交换，不改变线性表
    {
        tmp = q.data[mid];
        q.data[mid] = q.data[mid+1];
        q.data[mid+1] = tmp;
    }
    if(high<low)
    {
        int n = q.len-1;
        while(n>=low)
        {
            q.data[n+1] = q.data[n];
            n--;
        }
        q.data[low] = x;// low 指向插入位置，high+1指向插入位置
        q.len++;
    }
}

int main()
{
    seqlist q;
    int x;

    q = {2,3,6,7,9,10,12,14,16,17};
    q.len = 10;
    printf("input x = ");
    scanf("%d",&x);
    printf("q.len = %d\n",q.len);
    binary(q,x);
    printf("q.len = %d\n",q.len);
    for(int i=0;i<q.len;i++)
    {
        printf("q.data[%d] = %d\n",i,q.data[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

2.统考真题

10. 设将$n(n>1)$个整数存放到一维数组$R$中。设计一个在时间和空间两方面都尽可能高效的算法。将$R$中保存的序列循环左移$p(0<p<n)$个位置，即将$R$中的数据由$(X_0，X_1\dots ，X_{n-1})$变换为$(X_p,X_{p+1}\dots ,X_{n-1},X_0,X_1\dots \dots X_{p-1})$
    算法思想：

此题类似第8题，可看成两个数组，先将前半部分逆置，再将剩下部分逆置，最后整体逆置
数学表达式解释：$(a^{-1}{b}^{-1}{)}^{-1}=(ba)$

// 10. 设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间
// 两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，
// 即将R中的数据由(X0，X1…，Xn-1)变换为(Xp,Xp+1…,Xn-1,X0,X1…… Xp-1)
#include<stdio.h>

void reverse(int a[],int left,int right)
{
    int tmp;
    while(left<right)
    {
        tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        left++;
        right--;
    }
}

void exchange(int a[],int p,int n)
{
    reverse(a,0,p-1);
    reverse(a,p,n-1);
    reverse(a,0,n-1);
}

int main()
{
    int a[11] = {11,12,13,14,15,23,24,25,26,27,28};
    exchange(a,5,11);
    for(int i=0;i<11;i++)
    {
        printf("a[%d] = %d\n",i,a[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

注：

1. 时间复杂度：$O(n)$, 空间复杂度$O(1)$
2. 法二：借助数组，将前$p$个元素放入新数组中，原数组左移，然后将新数组中$p$个元素放到原数组尾部，时间复杂度：$O(n)$, 空间复杂度$O(p)$

11. 一个长度为$L(L>=1)$的升序序列$S$，处在第$\lceil L/2\rceil$个位置的数称为$S$的中位数。例如，若序列$S1=(1,13,15,17,19)$，则$S_1$的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若$S_2=(2,4,6,8,20)$，则$S_1$和$S_2$的中位数是11.现在有两个等长升序序列$A$和$B$，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列$A$和$B$的中位数。
    算法思路：

题目要求两序列等长，所以与博客上寻找第$k$个值稍有差别，是简化版

1. 设计函数，定义$a，b$的起始位置即中间位置$s1,d1,m1,s2,d2,m2$, 在$s1!=d1||s2!=d2$的情况下
2. 判断两数组中位数的大小（若$a[m1]>b[m2]$），若相等直接返回此数即为中位数，判断中位数较小的数组内为奇数还是偶数，改变数组起始位置，舍去小于$b[m2]$，大于$a[m1]$的元素（因为不存在中位数存在与$a[0$ ~$m1],b[m2$~$n-1]$中），舍去元素个数要相等，继续循环
3. 退出循环后，返回$a[s1],b[s2]$中较小的数为中位数

// 一个长度为L(L>=1)的升序序列S，处在第L/2个位置的数称为S的中位数。
// 例如，若序列S1=(1,13,15,17,19)，则S1的中位数是15，两个序列的中位数是含它们所有
// 元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11.现在有两个
// 等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

//题目规定等长的两个序列，思路如下
//1.比较a[k/2]与b[k/2],
//若a[k/2]<b[k/2] 则删除a[0-k/2],b[k/2-n],同时两段舍弃长度相等
//因为a[k/2]<b[k/2]说明a[0-k/2]小于b[k/2],合并后的中位数第k个元素不可能出现在a[0]-a[k/2]这个区间
//若a[k/2]>b[k/2] 则删除a[k/2-n],b[0-k/2],同时两段舍弃长度相等
//当a[k/2]=b[k/2]时，即为所求中位数
#include<stdio.h>

int m_search(int a[], int b[], int n)
{
    int s1 = 0, d1 = n-1, m1, s2 = 0, d2 = n-1, m2;
    while(s1!=d1||s2!=d2)
    {
        m1 = (s1+d1)/2;
        m2 = (s2+d2)/2;
        if(a[m1] == b[m2])
        {
            return a[m1];
        }
        if(a[m1]<b[m2])
        {
            if((s1+d1)%2==0)//奇数
            {
                s1 = m1;
                d2 = m2;
            }
            else
            {
                s1 = m1+1;
                d2 = m2;
            }
        }
        else
        {
            if((s2+d2)%2==0)
            {
                s2 = m2;
                d1 = m1;
            }
            else
            {
                s2 = m2+1;
                d1 = m1;
            }
        }
    }
    printf("m1 = %d, m2 = %d, s1 = %d, s2 = %d\n",m1, m2, s1, s2);
    printf("a[m1] = %d, a[s1] = %d, b[m2] = %d, b[s2] = %d\n",a[m1], a[s1] ,b[m2], b[s2]);
    //当s1==d1 或 s2==d2 时，跳出循环，所以不会重新计算m1,m2的值，
    // 所以此时m1,m2 的值并不是更新后的值，所以要比较s1,s2 的大小
    if(a[s1]<b[s2])
    {
        return a[s1];
    }
    else return b[s2];
}

int main()
{
    int a[5] = {11,13,15,17,19};
    int b[5] = {2,4,6,8,20};
    int n = 5;

    int res = 0;
    res = m_search(a,b,n);
    printf("res = %d",res);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

注：

1. 退出循环返回中位数时，返回的是$a[s1]/b[s2]$的值，当$s1==d1$ 或 $s2==d2$ 时，跳出循环，所以不会重新计算$m1,m2$的值，所以此时$m1,m2$ 的值并不是更新后的值，所以要比较$s1,s2$ 的大小
2. $a[m1]<b[m2]$舍弃$a$中的较小一半，舍弃$b$中较大的一半，两次舍弃的长度相等。
3. 时间复杂度：$O(lo{g}_{2}n)$（看到log级别的肯定想到二分查找），空间复杂度$O(1)$

12. 已知一个整数序列$A=(a_0,a_1\dots ,a_{n-1})$，其中$0<a_i<n(0<i<n)$.若存在$a_{p1}=a_{p2}=...=a_{pm}=x$且$m>n/2(0<p_k<n，l<=k<=m)$，则称$x$为$A$的主元素。例如$A=(0,5,5,3,5,7,5,5)$，则5为主元素；又如$A=(0,5,5,3,5,1,5,7)$，则$A$中没有主元素。假设$A$中的$n$个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出$A$的主元素。若存在主元素，则输出该元素；否则输出-1。
    算法思想1：

1. 扫描数组，$c$存储当前元素，后一元素与当前元素相等，计数加一，否则计数减一，计数为0时，$c$中放入下一元素，重新开始计数
2. 判断是否存在计数不为0的数，若存在，重新扫描数组，重新统计$c$的个数，判断是否为主元素，并返回元素
3. 时间复杂度：$O(n)$, 空间复杂度：$O(1)$

算法思想2：

1. 先通过快速排序，将数组重新排序
2. 判断元素连续出现的次数，若出现次数大于$n/2$的元素跳出循环，返回值，否则返回0；

// 已知一个整数序列A=(a0,a1…,an-1)，其中0<ai<n(0<i<n).
// 若存在ap1 = ap2 = ... = apm = x且m>n/2(0<pk<n，l<=k<=m)，则称x为A的主元素。
// 例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。
// 假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。
//算法思想：
// 扫描数组，遇到第一个数num存入c中，计数加一，下一个数为num则计数加一，若不是则减一，当num为0时，c中保存下一整数，
//重新扫描，判断c中元素是否为数组主元素

#include<stdio.h>

int majority1(int a[], int n)
{
    int c = a[0] ,count = 1;
    for(int i=1;i<n;i++)
    {
        if(count){
            if(a[i] == c)
            {
                count++;
            }
            else count--;
        }
        else 
        {
            count = 1;
            c = a[i];
        }
    }
    if(count>0)//排除不必要的循环，先确定是否有出现多次的元素值
    {
        count = 0;
        for(int j=0;j<n;j++)
        {
            if(a[j] == c)
            {
                count++;
            }
        }
    }
    if(count>n/2) return c;
    else return 0;
}

int partition(int a[], int low, int high)
{
    int pos = a[low];
    while(low<high)
    {
        while(low<high&&a[high]>=pos) {high--;}
        a[low] = a[high];
        while(low<high&&a[low]<=pos) {low++;}
        a[high] = a[low];
    }
    a[low] = pos;
    return low;
}

void  quick_sort(int a[],int low,int high)
{
    if(low<high)
    {
        int pos = partition(a,low,high);
        quick_sort(a,low,pos-1);
        quick_sort(a,pos+1,high);
    }
}

void print_a(int a[], int n){
    for(int i = 0;i<n;i++){
        printf("  %d  ",*(a+i));
    }
    printf("\n");
}

int majority2(int a[],int n)
{
    print_a(a,n);
    
    quick_sort(a,0,n-1);
    print_a(a,n);
    int count = 1;
    int c = a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i] == a[i-1])
        {
            count++;
            if(count>n/2)
            {
                break;
            }
        }
        else
        {
            c = a[i];
            count = 1;
        }
    }
    if(count>n/2) return c;
    else return 0;
}

int main()
{
    int a[8] = {0,5,5,3,5,7,5,5};
    int n = 8;
    int res1 = majority1(a,n);
    printf("res1 = %d\n",res1);
    int res2 = majority2(a,n);
    printf("res2 = %d\n",res2);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

13. 给定一个含$n(n>=1)$个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。
    算法思想：

利用空间换时间
新建数组，用于标记，遍历一次初始数组，遍历一次标记数组，时间复杂度为$O(n)$空间复杂度为$O(n)$

// 给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。
// 例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。
#include<stdio.h>

int findmissmin(int a[], int n)
{
    int b[30] = {0};
    int min = 0;
    for(int i=0;i<n;i++)
    {
        int t = a[i];
        b[t] = 1;
    }
    for(int i=1;i<30;i++)
    {
        if(b[i]==0) 
        {
            min = i;
            break;
        }
    }
    return min;
}

int main()
{
    int a[4] = {-1,2,3,4};
    int n = 4;
    int res ;
    res = findmissmin(a,n);
    printf("res = %d",res);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34