第一周练习——认识复杂度和简单排序算法-创新互联-乐山大橙子建站

新闻中心

这里有您想知道的互联网营销解决方案

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

前言：
👏作者简介：我是笑霸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元起，快前往官网查看详情吧
                                                

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

                                                文章源于：http://lswzjz.com/article/dpepje.html


                                            
                                                
                                                    其他资讯
                                                
                                                
                                                    
                                                        
                                                                TP5.1如何引入public下的CSS和JS文件-创新互联
                                                            

                                                                css怎么设置字母的大小写-创新互联
                                                            

                                                                linux启动dhcp服务器的方法-创新互联
                                                            

                                                                html中引入css样式的方法-创新互联
                                                            

                                                                退出postgresql数据库的方法-创新互联