王道数据结构2022版本

2.2.3.10

算法思想

创建辅助数组s，先将R数组中前p个元素放入辅助数组s，再将R后n-p个元素左移p(0<p<n)个位置，然后将s中暂存的p个元素放到R数组的后面

算法流程

1. 先创建辅助数组s并初始化为0。
2. 再遍历R数组。当i<p时，将R[i]放入s数组，并且将R[i]=R[i+p]移动一个后面的元素，当i>=p时,不再将元素放入s数组，而是单纯的移动。
3. 将然后将s中暂存的p个元素放到R数组的后面，R[i]=s[i-n+p]

算法实现

void converse(int R[],int n,int p)
{
    int s[p]={0}; //初始化辅助数组，并赋值为0
    int i;
    for(i=0;i<n;i++) //遍历R数组，部分暂存于s，部分左移
    {
        if(i<p) s[i]=R[i];
        R[i]=R[i+p];
    }
    for(i=n-p;i<n;i++) R[i]=s[i-n+p]; //将暂存在s的元素，放回R后面
}

测试代码

#include<iostream>

using namespace std;

void converse(int R[],int n,int p)
{
    int s[p]={0}; //初始化辅助数组，并赋值为0
    int i;
    for(i=0;i<n;i++) //遍历R数组，部分暂存于s，部分左移
    {
        if(i<p) s[i]=R[i];
        R[i]=R[i+p];
    }
    for(i=n-p;i<n;i++) R[i]=s[i-n+p]; //将暂存在s的元素，放回R后面
}
int main()
{
    int a[]={1,2,3,4,5,6,7,8,9};
    converse(a,9,4);
    for(int i=0;i<9;i++) cout<<a[i]<<' ';
    return 0;
}

2.2.3.11

算法思想

创建辅助数组c[2*n],用来存储数组a[]、b[]中的所有元素，使用排序算法对数组c[]进行排序，再取第n个数就是中位数了(题目中对中位数的定义)

算法流程

从c[0]开始为c数组赋值，当i<n时，c[i]=a[i],否则，c[i]=b[i]。赋值完毕之后，使用快速排序算法对c数组进行排序。排序完成之后，返回c[n-1]。

算法实现

void quick_sort(int a[], int l,int r)
{
    if(l>=r) return;
    int x=a[(l+r)/2], i=l-1,j=r+1;
    int tmp;
    while(i<j){ 
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) {tmp=a[i];a[i]=a[j];a[j]=tmp;}
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
}
int mid_search(int a[],int b[],int n)
{
    int c[2*n]={0};  //辅助数组初始化为0
    int i;
    for(i=0;i<2*n;i++) //为辅助数组赋值
    {
         if(i<n) c[i]=a[i];
         else c[i]=b[i-n];
    }
    quick_sort(c,0,2*n-1); //进行排序
    return c[n-1]; //返回中位数
}

测试代码

#include<iostream>

using namespace std;

void quick_sort(int a[], int l,int r) //快排模板
{
    if(l>=r) return;
    int x=a[(l+r)/2], i=l-1,j=r+1;
    int tmp;
    while(i<j){ 
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) {tmp=a[i];a[i]=a[j];a[j]=tmp;}
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
}
int mid_search(int a[],int b[],int n)
{
    int c[2*n]={0};  //辅助数组初始化为0
    int i;
    for(i=0;i<2*n;i++) //为辅助数组赋值
    {
         if(i<n) c[i]=a[i];
         else c[i]=b[i-n];
    }
    quick_sort(c,0,2*n-1); //进行排序
    return c[n-1]; //返回中位数
}
int main()
{
    int a[]={11,13,15,17,19};
    int b[]={2,4,6,8,20};
    cout<<mid_search(a,b,5);
    return 0;
}

2.2.3.12

算法思想

分配一个用于计数的数组st[n],用来记录a中元素出现的次数，st[i]=j表示元素a[i]出现了j次，如果出现次数最多的元素符合众数定义，返回就好

算法流程

1. 创建辅助数组并赋值为0，用于对元素计数
2. 遍历数组a，对元素出现次数进行累加
3. 遍历辅助数组 寻找出现次数最多的数
4. 判断是否满足众数的要求，满足则返回，不满足返回-1

算法实现

int majority(int a[],int n)
{
    int st[n]={0}; //辅助数组初始化为0
    int i,major=0; //初始化 0 是出现次数最多的元素
    for(i=0;i<n;i++) //遍历a数组
    {
        st[a[i]]++;
    }
    for(i=1;i<n;i++) //遍历辅助数组 寻找出现次数最多的数
        if(st[i]>st[major]) major=i;
    return st[major]>n/2?major:-1; //判断是否满足众数的要求
}

测试代码

#include<iostream>

using namespace std;

int majority(int a[],int n)
{
    int st[n]={0}; //辅助数组初始化为0
    int i,major=0; //初始化 0 是出现次数最多的元素
    for(i=0;i<n;i++) //遍历a数组
    {
        st[a[i]]++;
    }
    for(i=1;i<n;i++) //遍历辅助数组 寻找出现次数最多的数
        if(st[i]>st[major]) major=i;
    return st[major]>n/2?major:-1; //判断是否满足众数的要求
}

int main()
{
    int a[]={0,4,4,3,4,7,4,4};
    int b[]={0,5,5,3,5,1,5,7};
    cout<<majority(b,8);
    return 0;
}

2.2.3.13

算法思想

见王道书

算法流程

见王道书

算法实现

int find_miss_min(int a[],int n)
{
    int st[n]={0}; //初始化辅助数组并赋值
    int i;
    for(i=0;i<n;i++) //遍历a数组，并添加标记
    {
        if(a[i]>0 && a[i]<n+1)
            st[a[i]-1]=1;
    }
    for(i=0;i<n;i++) //找到第一个没有被标记的
        if(st[i]==0) break;
    return i+1; //如果没找到没被标记的 就返回n+1
}

测试代码

#include<iostream>

using namespace std;

int find_miss_min(int a[],int n)
{
    int st[n]={0}; //初始化辅助数组并赋值
    int i;
    for(i=0;i<n;i++) //遍历a数组，并添加标记
    {
        if(a[i]>0 && a[i]<n+1)
            st[a[i]-1]=1;
    }
    for(i=0;i<n;i++) //找到第一个没有被标记的
        if(st[i]==0) break;
    return i+1; //如果没找到没被标记的 就返回n+1
}

int main()
{
    int a[]={-5,3,2,3};
    int b[]={1,2,3};
    cout<<find_miss_min(b,4);
    return 0;
}

1

算法思想

算法流程

算法实现

测试代码

1

算法思想

算法流程

算法实现

测试代码

1

算法思想

算法流程

算法实现

测试代码