第一周练习——认识复杂度和简单排序算法-创新互联

前言：
�作者简介：我是笑霸final，一名热爱技术的在校学生。
�个人主页：个人主页1 || 笑霸final的主页2
�系列专栏：《数据结构与算法》
�如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步�
�如果感觉博主的文章还不错的话，�点赞� + �关注� + �收藏�

创新互联建站是工信部颁发资质IDC服务器商，为用户提供优质的成都天府联通服务器托管服务

在这里插入图片描述

请添加图片描述

目录
  • 随堂习题-排序（冒泡排序）
  • 随堂习题-排序（选择排序）
  • 随堂习题-排序（插入排序）
  • 随堂习题-二分查找某数
  • 随堂习题-查找某个位置
  • 随堂习题-局部最小值问题
  • 随堂习题-一个数出现奇数次
  • 随堂习题-两个数出现奇数次
  • 随堂习题-（递归）数组中的大值

随堂习题-排序（冒泡排序）

给你一个n代表有n个数字，给出这n个数字，然后你需要使用冒泡排序将这些数字从小到大排好。

输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //冒泡
    for(int i=n-1;i>0;i--){for(int j=0;jif(nums[j]>nums[j+1]){nums[j]  =nums[j] ^ nums[j+1];
                nums[j+1]=nums[j] ^ nums[j+1];
                nums[j]  =nums[j] ^ nums[j+1];
            }
        }
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}
随堂习题-排序（选择排序）

给你一个n代表有n个数字，然后你需要使用选择排序将这些数字从小到大排好。
输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //选择排序
    
    for(int i=0;iint vauleMinIndex=i;
        for(int j=i+1;jif(nums[vauleMinIndex]>=nums[j]){vauleMinIndex=j;
            }
        }
        swap(nums[i], nums[vauleMinIndex]);
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}
随堂习题-排序（插入排序）

给你一个n代表有n个数字，然后你需要使用插入排序将这些数字从小到大排好。
输入描述:

第一行输入一个n，代表有n个数字
第二行输入n个数

输出描述:

输出排序好后的n个数

示例1
输入:

4
4 3 2 1

输出:

1 2 3 4

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;icin >>nums[i];
    }
    //插入排序
    for(int i=0;ifor(int j=1;jif(nums[j]swap(nums[j],nums[j-1]);
            }
        }
    }
    //输出
     for(int i=0;icout<< nums[i]<<" ";
    }
    return 0;
}
随堂习题-二分查找某数

给你一个n代表有一个长度为n的有序数组，然后给你一个k，你需要判断这个k是否在数组里面，
如果存在就返回这个数从左往右第一次出现位置的下标，如果不存在输出-1。
输入描述:

第一行输入一个n，k，其中n代表有n个数字，k代表你需要查找的元素
第二行输入n个数

输出描述:

如果在数组里面找到了k，输出k所在的下标（注：如果数组中k出现了多次，请输出最小的下标！），如果k不在，就输出-1

示例1
输入:

7 0
0 1 2 3 4 5 6

输出:

0

代码

#include#includeusing namespace std;
int main(){int n=0,k=-1,tep=-1;
    cin>>n;cin>>k;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;i>nums[i];
    
    for(int i=0;i//插入排序
        for(int j=1;jif(nums[j]//交换两个数
                nums[j]  = nums[j] ^ nums[j-1];
                nums[j-1]= nums[j] ^ nums[j-1];
                nums[j]  = nums[j] ^ nums[j-1];
            }
        }
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]<  k) l=mid+1;
        if(nums[mid] >k) r=mid-1;
        if(nums[mid] == k){//查重
            if(nums[mid-1]< nums[mid]){tep = mid;
            }
             r= mid-1;
        }
    }
    cout<
随堂习题-查找某个位置

你需要输入一个n，一个数k，然后输入一个长度为n个大小的数组arr，然后你需要在arr上找满足>=K的最左位置，并且输出这个位置，如果不存在这个位置就输出-1。
输入描述:

第一行输入一个n，k
第二行输入长度为n个大小的数组arr

输出描述:

输出>=K的最左位置

示例1
输入:

5 1
0 0 2 4 6

输出:

2

代码

#include#includeusing namespace std;
int main(){int n=0,k=-1,tep=-1;
    cin>>n;cin>>k;
    if(n<=0) return 0;
    vectornums(n);
    for(int i=0;i>nums[i];
    
    for(int i=0;i//插入排序
        for(int j=1;jif(nums[j]//交换两个数
                nums[j]  = nums[j] ^ nums[j-1];
                nums[j-1]= nums[j] ^ nums[j-1];
                nums[j]  = nums[j] ^ nums[j-1];
            }
        }
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]<  k) l=mid+1;
        if(nums[mid] >k){r=mid-1;
            tep=mid;
        } 
        if(nums[mid] == k){tep=mid;
            //查重
            if(nums[mid-1] >nums[mid]){tep = mid;
            }
             r= mid-1;
        }
    }
    cout<
随堂习题-局部最小值问题

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]< arr[1]，那么arr[0]是局部最小；
如果arr[N-1] 是局部最小。给定无序数组arr,已知arr中任意两个相邻的数都不相等，只需要返回arr中任意一个局部最小出现的位置即可，如果不存在这个位置就输出-1。

输入描述:

第一行输入一个n代表下面需要输入n个数
第二行输入n个元素，任意两个相邻的数都不相等

输出描述:

返回arr中任意一个局部最小出现的位置

示例1
输入:

6
6 2 3 1 5 6

输出:

1

代码

#include#includeusing namespace std;
int main(){int n=0;
    cin>>n;
     if(n<=0) { cout<< -1<< endl;
        return 0;
    }
    vectornums(n);
    for(int i=0;i>nums[i];
   
    //开头局部最小
   if(n==1 || nums[0]< nums[1]){cout<< 0<< endl;
        return 0;
   }
    if(n==2 && nums[0]>nums[1]){cout<< 1<< endl;
        return 0;
    }
    //末尾局部最小
    if (nums[n-1]< nums[n-2]){cout<< n - 1<< endl;
        return 0;
    }
   //二分查找
    int l=0,r=n-1;
    while(l<= r){int mid = l + ((r -l ) >>1);
        if(nums[mid]< nums[mid-1] && nums[mid]cout<< mid<< endl;
            return 0;
        }
        else if( nums[mid]//说明mid+1也小于于mid  所以局部最小值应该在右边
            l=mid+1;
        }
        else  r=mid-1;
    }
    cout<<-1;
    return 0;
}
随堂习题-一个数出现奇数次

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数？

输入描述:

第一行输入一个n代表，有个n个长度大小的数组
第二行输入一个长度为n的数组

输出描述:

输出这个数组中出现奇数次的数

示例1
输入:

5
1 1 1 2 1

输出:

2

代码

#includeusing namespace std;
 int main(){ int n=0;
     cin>>n;
     if(n<=0){ cout<<-1;
         return 0;
     }
     vectorarr(n);
     for(int i=0;i>arr[i];
     
     int x=0;
     for(int i=0;i x=x^arr[i];
     }
     cout<< x<
随堂习题-两个数出现奇数次

给定一个数字arr，其中只有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

输入描述:

第一行输入一个n，
第二行输入n个数

输出描述:

输出出现奇数次的两个数，按照从小到大的顺序。

示例1
输入:

4
1 1 2 3

输出:

2 3

代码

#includeusing namespace std;
 int main(){ int n=0;
     cin>>n;
     if(n<=0){ cout<<-1;
         return 0;
     }
     vectorarr(n);
     for(int i=0;i>arr[i];
     //如果所有的数异或运算 最后的值一定是出现奇数次的两个数的异或 并且一定不为0 
     //例如1111 和 1000 他们异或 为 0111
     int eor=0;
     
     for(int i=0;i //把和rightOne位置同为1的数异或 那么得到的数就是其中的一个答案
        if( (rightOne & arr[i]) != 0){onlyOne ^= arr[i];
        }
     }
    int y= eor^onlyOne;
        if(onlyOne  cout<< onlyOne<<" "<< y;
        }else{ cout<< y<<" "<< onlyOne;
        }
     return 0;
 }
随堂习题-（递归）数组中的大值

用递归方法找一个数组中的大值

输入描述:

第一行输入一个n，代表数组的长度
第二行，输入n个数

输出描述:

输出这个数组中的大值

示例1
输入:

5
1 2 3 4 5

输出:

5

代码

#include#includeusing namespace std;

//递归
int myMax(int arr[],int l,int r){if(l==r){return arr[l];
    }
    int mid=l+((r-l)>>1);
    int leftmax=myMax(arr,l,mid);
    int rightmax=myMax(arr,mid+1,r);
    return leftmax >rightmax ? leftmax : rightmax;
}

int main(){int n;
    cin>>n ;
    if(n<=0) return 0;
     int *arr = new int[n];
    //vectorarr(n);
    for(int i = 0 ;i< n ; i++){cin>>arr[i];
    }
    cout<< myMax(arr,0,n-1);
    return 0;
}

注意
上述例题来自牛客网 https://www.nowcoder.com/

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：第一周练习——认识复杂度和简单排序算法-创新互联
分享链接：/article24/dpepje.html

成都网站建设公司_创新互联，为您提供用户体验、微信小程序、App开发、网站内链、关键词优化、微信公众号

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

成都网站建设

网站导航知识

分类信息网

2024欧洲杯竞猜官网 | BET体育官方网站（中国）有限公司 | 星空体育·(StarSky Sports) | bet官方（中国）有限公司 | 在线体育竞猜(中国)有限公司 | BET体育|中国有限公司 | bat365在线平台·(中国)官方网站 | 半岛·体育（中国）官方网站 |