首页 > 编程语言 >信息学奥赛初赛天天练-20-完善程序-vector数组参数引用传递、二分中值与二分边界应用的深度解析

信息学奥赛初赛天天练-20-完善程序-vector数组参数引用传递、二分中值与二分边界应用的深度解析

时间:2024-06-06 09:01:29浏览次数:17  
标签:二分 right 20 nums int mid 初赛 vector left

PDF文档公众号回复关键字:20240605
在这里插入图片描述

1 2023 CSP-J 完善程序1

完善程序(单选题,每小题 3 分,共计 30 分)

原有长度为 n+1,公差为1等升数列,将数列输到程序的数组时移除了一个元素,导致长度为 n 的开序数组可能不再连续,除非被移除的是第一个或最后之个元素。需要在数组不连续时,找出被移除的元素。试补全程序。

源程序

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int find_missing(vector<int>& nums){
07 		int left = 0, right = nums.size() - 1;
08 		while (left < right){
09   		int mid = left + (right-left) / 2;
10   		if (nums[mid]==mid+ ①){
11        		②;
12    		}else{
13      		③
14    		}
15   	}
16  	return ④;
17 }
18
19 int main(){
20 		int n;
21 		cin >> n;
22 		vector<int> nums(n);
23 		for (int i= 0; i< n; i++) cin >> nums[i];
24 		int missing_number = find_missing(nums);
25 		if(missing_number == ⑤) {
26     		cout << "Sequence is consecutive" << endl;
27 		}else{
28    		cout << "Missing number is " << missing_number << endl;
29 	    }
30 		return 0;
31 }

33 ①处应填( )

A 1 B nums[0] C right D left

34 ②处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

35 ③处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

36 ④处应填( )

A left+nums[0] B right+nums[0] C mid+nums[0] D right+1

37 ⑤处应填( )

A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]

2 相关知识点

1) vector 参数传递-值传递

函数内形参改变对调用实参无影响

#include<bits/stdc++.h>
using namespace std;

/*
  值传递 
  函数内增量了副本 函数内修改 对实参无影响 
*/ 
void testVector(vector<int> vec){
	vec.push_back(4); 
	/*
	 输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4
	 输出 2 2 2 4 
	*/ 
	for(int i=0;i<vec.size();i++){
    	cout <<vec[i]<< ' ';
	}
}

int main(){
	vector<int> vec(3,2);//声明一个vector数组,初始化3个2 
	testVector(vec);//调用函数输出 
	cout<<endl; 
	//testVector 增加的4 对main函数的vec没影响
	/*
	 输出vec数组中每个元素3个2
	 输出 2 2 2 
	*/ 
	for(int i=0;i<vec.size();i++){
    	cout <<vec[i]<< ' ';
	}
	return 0;
}


2) vector 参数传递-指针传递

函数内形参改变,改变了调用的实参

#include<bits/stdc++.h>
using namespace std;

/*
  指针传递 
  函数操作的是vector指针,通过指针对vector数组修改后vector被改变 
*/ 
void testVector(vector<int> *vec){
	(*vec).push_back(4); 
	/*
	 输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4
	 输出 2 2 2 4 
	*/ 
	for(int i=0;i<(*vec).size();i++){
    	cout <<(*vec)[i]<< ' ';
	}
}

int main(){
	vector<int> vec(3,2);//声明一个vector数组,初始化3个2 
	testVector(&vec);//调用函数输出 
	cout<<endl; 
	//testVector 增加了4 
	/*
	 输出vec数组中每个元素3个2和 4
	 输出 2 2 2 4
	*/ 
	for(int i=0;i<vec.size();i++){
    	cout <<vec[i]<< ' ';
	}
	return 0;
}

3) vector 参数引用传递

函数内形参改变,改变了调用的实参

#include<bits/stdc++.h>
using namespace std;

/*
  指针传递 
  形参相当于是实参的别名,对形参的操作其实就是对实参的操作,形参vector改变,实参也会改变 
*/ 
void testVector(vector<int> &vec){
	vec.push_back(4); 
	/*
	 输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4
	 输出 2 2 2 4 
	*/ 
	for(int i=0;i<vec.size();i++){
    	cout <<vec[i]<< ' ';
	}
}

int main(){
	vector<int> vec(3,2);//声明一个vector数组,初始化3个2 
	testVector(vec);//调用函数输出 
	cout<<endl; 
	//testVector 增加了4 
	/*
	 输出vec数组中每个元素3个2和 4
	 输出 2 2 2 4
	*/ 
	for(int i=0;i<vec.size();i++){
    	cout <<vec[i]<< ' ';
	}
	return 0;
}

4) 二分查找中间值

/* 向右逼近,如果找到满足条件的数,会继续向右找更大的数
   mid=(left+right)/2 left和right都接近最大值时,可能溢出可以使用下面写法替换
   mid=left + (right-left) / 2;
*/
    
/* 向左逼近,如果找到满足条件的数,会继续向左找更小的数
   mid=(left+right+1)/2 left和right都接近最大值时,可能溢出可以使用下面写法替换
   mid=left + (right-left+1) / 2;
*/

5) 二分找边界

//左闭右闭 while left right 最终left=right+1
while(left<=right)  left = mid + 1; right =mid-1;
//左闭右开 while left right 最终left=right
while(left<right)   left = mid + 1; right =mid;
//左开右闭 while left right 最终left=right
while(left<right)   left=mid;       right=mid+1;
//左开右开 while left right 最终left=right-1
while(left+1<right) left=mid;       right=mid;

3 思路分析

二分法,在本程序中find_missing函数就是利用二分法来找到一个长度为n的数组中不连续的位置,从而找出被移除 元素的值。只需通过二分找到从左往右第一处使得nums[i]不为nums[0]+i的的位置,那么在数组中被移除的数就是nums[0]+i

33 ①处应填( )

A 1 B nums[0] C right D left

答案 B

分析

/*
若数组连续, 一定有nums[i]==nums[0]+i,所以只需通过二分找到第一处使得nums[i]不为nums[0]+i的的位置即可。因此二分的判断条件是nums[mid]==mid+nums[0]

所以选B
*/

34 ②处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

答案 A

分析

//由判断条件 nums[mid]==mid+nums[0] 可知,mid的左半部分是满足顺序的,继续往右找

//由于mid计算是向下取整,需要向右靠近 所以left=mid+1
//int mid = left + (right-left) / 2; mid计算是向下取整 需要left=mid+1,向右逼近
int find_missing(vector<int>& nums){
		int left = 0, right = nums.size() - 1;
		while (left < right){
  		int mid = left + (right-left) / 2;
  		if (nums[mid]==mid+nums[0]){
       		left=mid+1;//找到满足条件的继续向右找
   		}else{
     		right=mid;
   		}
  	}
 	return left+nums[0];
}
//nums={0,1,3,4,5} 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2
*/

//int mid = left + (right-left) / 2; mid计算是向下取整 如果left=mid 可能会死循环
int find_missing(vector<int>& nums){
		int left = 0, right = nums.size() - 1;
		while (left < right){
  		int mid = left + (right-left) / 2;
  		if (nums[mid]==mid+nums[0]){
       		left=mid;//如果改成left=mid 会死循环
   		}else{
     		right=mid;
   		}
  	}
 	return left+nums[0];
}
//nums={0,1,3,4,5}时会死循环 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 满足 while(left<right)
mid=(1+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 满足 while(left<right)
*/

35 ③处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

答案 C

分析

/*
由于退出条件是 while (left < right) 最终退出时left==right ,前面又 left=mid+1,所以right==mid即可

while(left<right) 对应 二分区间是前闭后开或者前开后闭
*/

36 ④处应填( )

A left+nums[0] B right+nums[0] C mid+nums[0] D right+1

答案 A

分析

//如果序列从0开始,最后1个找到的连续数字再找一个就是被移除的,前面示例
//nums={0,1,3,4,5} 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2
移除的数是2
*/

//如果不从0开始
//nums={2,3,5,6,7}
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=5,mid+nums[0]=2+2=4 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=3,mid+nums[0]=1+2=3 相等 left=mid+1=2 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2+2=4
移除的数是4
*/
//退出条件是while(left<right) 最终left==right
//所以答案A和B都对,一般习惯返回left

37 ⑤处应填( )

A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]

答案 D

分析

找到数组的最后一个,无论最后一个是否相等都说明前面都是连续的

标签:二分,right,20,nums,int,mid,初赛,vector,left
From: https://blog.csdn.net/ya888g/article/details/139482811

相关文章

  • 2024年6月 AWVS -24.4.27详细安装教程附下载教程含windows和linux多版本
    免责声明请勿利用文章内的相关技术从事非法测试。由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,作者不为此承担任何责任,请务必遵守网络安全法律法规。本文仅用于测试,请完成测试后24小时删除,请勿用于商业用途。如文中内容涉及侵权......
  • 【高质量】2024年数学建模国赛A题保奖思路(点个关注,后续会更新)
    您的点赞收藏是我继续更新的最大动力!一定要点击如下的卡片链接,那是获取资料的入口!点击链接加入群聊【2024国赛资料合集】:http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=i9iTpd5r3L546ho71Fv5Ml5JNPODziWg&authKey=0vIFaOH5PnDnmvvkstjxvIoD6S919ufxy2Y7AxbtgmgESZAFaSOwqlP73Jx......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素(数组)
    第一次打卡,记录还不够充分,会慢慢丰富起来一、二分查找题目链接:704.二分查找-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想录讲解 情况1:左闭右闭区间情况2:左闭右开区间 二、移除元素题目链接:27.移除元素-力扣(LeetCode)讲解链接:Carl讲解视频讲解:代码随想......
  • 代码随想录算法训练营第一天 | 704. 二分查找,27. 移除元素
    题目链接:704.二分查找思路:该题为有序数组查找,采用二分法。根据区间分为左闭右闭和左闭右开两种情况坑:左右区间的开闭补充:vector容器时间复杂度:O(logn)空间复杂度:O(1)题目链接:27.移除元素思路:题目说返回k个元素之后留下什么不重要,也不考虑数组剩下元素的......
  • 【软件插件】SketchUP插件-最新版坯子插件2024 v3.2.2(支持SketchUp2012-2024版本)安装
    下载链接:https://r0vr8xquwul.feishu.cn/docx/MXC5dUMZroLibaxYgZ3cmkyinDe详细图文教程:https://www.yuque.com/zhefengerhuanzaigua/bld6x5/kc2baq1msy6dehb3软件介绍坯子插件库是为SketchUp(草图大师)用户推出的一款插件管理工具,我们知道在使用sketchup进行模型设计的时候是......
  • 4.20
    开始制作有关视频播放的内容<template><view><swiperclass="swiper"autoplay="false"vertical="true"interval="990000"@change="changeVideo"><swiper-itemv-for="(item,index)invideo_list&q......
  • .NET周刊【6月第1期 2024-06-02】
    国内文章一文带你了解.NET能做什么?https://www.cnblogs.com/Can-daydayup/p/18214473.NET是一个免费、开源、跨平台的开发平台框架,广泛应用于桌面、Web、移动、云服务、游戏、物联网、大数据和人工智能等领域开发。它支持C#、VisualBasic、F#等多种编程语言,其中C#最为常用,通过......
  • 「清新题精讲」P2150 [NOI2015] 寿司晚宴
    P2150[NOI2015]寿司晚宴Statement给定\(n-1\)个数分别为\(2\simn\),从中选出交集为空的两个集合\(A,B\)(集合的并集不必须为\(\{2,\dots,n\}\),且集合可为空)使得不存在\(a\inA,b\inB\)满足\((a,b)\ne1\)(即任意两个数均互质),将方案数对\(p\)取模后输出。\(2\len\le......
  • 实验20-智能换脸
    changeface.pyimportcv2importdlibimportnumpyimportsysPREDICTOR_PATH="./shape_predictor_68_face_landmarks.dat"SCALE_FACTOR=1FEATHER_AMOUNT=11#代表各个区域的关键点标号FACE_POINTS=list(range(17,68))MOUTH_POINTS=list(range(48,61))RI......
  • Springboot框架开发与实用篇之热部署 2024详解
    开发与实用手动启动热部署热部署(HotDeployment)指的是在应用程序正在运行的情况下,对其进行更新或修改并将这些变更应用到正在运行的应用程序中的过程。通常情况下,传统的部署方式需要停止应用程序、部署更新,然后重新启动应用程序才能使更新生效。而热部署则允许在无需停止应用......