《编写一个函数来查找字符串数组中的最长公共前缀.docx》由会员分享,可在线阅读,更多相关《编写一个函数来查找字符串数组中的最长公共前缀.docx(4页珍藏版)》请在优知文库上搜索。
1、1、编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串o示例1:输入:rs=flower,flow,flight输出:W示例2:输入:btrs=dog,racecar,car:bw解麻:愉入不存在公共前缀。可以使用水平扫描法解决这个问题。我们将第一个字符串作为最长公共前缀的初始值,然后逐个比较后面的字符串与当前的公共前缀,更新公共前缀为两者的共同部分。如果最终的公共前缀为空字符串,则说明不存在公共前缀。具体步骤如下:如果输入字符串数组为空,直接返回空字符串。将第一个字符串设为初始的最长公共前缀。遍历数组中的每个字符串,将当前字符串与最长公共前缀进行比较,更新最长公共
2、前缀为两者的共同部分。如果最长公共前缀为空字符串,则直接返回空字符串。返回最长公共前缀作为结果。 1=h=200 0=strsi.length=200 strsi仅由小写英文字母组成#include#include#includeusingnamespacestd;stringIOngeStComrnOnPrefiX(VeCtOr&strs)if(O)return;)stringprefix=strsO;for(inti=l;i();i+)while(strsi.find(prefix)!=0)prefix=r(0,h()-1);if()return)returnprefix;)intmain
3、()vectorstrs=flower,flow,flight);stringresult=IongestCommonPrefix(Strs);coutLongestcommonprefix:,resultendl;returnO;)给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(IOgn)的算法。示例1:输入:nums=1,3,5,6,target=5输出:2输入:nums=1,3,5,6,target=2SU1区例3:输入:nums=1,3,5,6,target=7箔出:4可以使用二分查找算法
4、来解决这个问题。由于给定的数组是有序的,我们可以通过比较目标值与数组中间元素的大小,来确定目标值在数组中的位置。具体步骤如下:L初始化左边界left为0,右边界right为数组长度减1。2.当Ieft小于等于right时,执行以下步骤:2.1 计算中间位置mid,mid=(left+right)/2。2.2 如果目标值等于中间位置的元素numsmid,则返回mid。2.3 如果目标值小于中间位置的元素numsmid,则在左半边继续查找,更新右边界为midIo2.4 如果目标值大于中间位置的元素numsmid,则在右半边继续查找,更新左边界为mid+Io如果循环结束时仍未找到目标值,则返回lef
5、t,即将被按顺序插入的位置。时间复杂度分析:由于每次查找都将数组范围缩小一半,所以时间复杂度为0(logn)o 1=h=10fl -IOk=numsi素|的瓯排列数组 1(V=targetV=IOg#include#includeusingnamespacestd;intsearchlnsert(vector&nums,inttarget)intleft=O;intright=()-1;while(left=right)intmid=left+(right-left)/2;if(numsmid=target)returnmid;elseif(numsmidtarget)left=mid+1;elseright=mid-1;)returnleft;)intmain()vectornums=1,3,5,6;inttarget=5;intresult=searchlnsert(nums,target);coutInsertposition:,resultendl;returnO;