精华内容
下载资源
问答
  • 上一节我讲了冒泡排序,插入排序,选择排序这三种排序算法,我们的时间复杂度都是O(n^2),比较高,适合小规模数据的排序...我们可以借鉴这思想,来解决非排序的问题,比如:如何在O(n)的时间复杂度内查找一无序数...

    上一节我讲了冒泡排序,插入排序,选择排序这三种排序算法,我们的时间复杂度都是O(n^2),比较高,适合小规模数据的排序。今天,我讲两种时间复杂度为O(nlogn)的排序算法,归并排序和快速排序。这两种排序算法适合大规模的数据排序,比上一节讲的那三种排序算法要更常用。

    归并排序和快速排序都用到分治思想,非常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素?这就要用到我们今天要讲的内容。

    归并排序的原理

    我们先来看归并排序(Merge Sort)

    归并排序的核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

    7f2eeed99f492762e81107d6473c1255.png

    归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

    从我刚才的描述,你有没有感觉到,分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归实现的。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突。分治算法的思想我后面会有专门的一节来讲,现在不展开讨论,我们今天的重点还是排序算法。

    前面我通过举例让你对归并有了一个感性的认识,又告诉你,归并排序用的是分治思想,可以用递归来实现。我们现在就来看看如何用递归代码来实现归并排序

    我在讲递归代码的编写技巧你还记得吗?写递归代码的技巧就是,分析得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。所以,要想写出归并排序的代码,我们先写出归并排序的递推公式。

    递推公式:
    merge_sort(p...r) = merge( merge_sort(p...q), merge_sort(q+1...r) )
    终止条件:
    p >=r 不用再继续分解

    我来解释一下这个递推公式。

    mergesort(p..r)表示,给下标从p到r之间的数组排序。我们讲这个排序问题转化为了两个子问题merge_sort(p..q)和merge_sort(q+1,r),其中下标q等于p和r的中间位置,也就是(p+r)/ 2。当下标从p到q和从p+1到r这两个子数组都排好序之后,我们再将两个子序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

    有了递推公式,转化成代码就简单多了。为了阅读方便,我这里只给出伪代码,你可以翻译成为你熟悉的编程语言。

    // 归并排序算法,A是数组,n表示数组大小
    merge_sort(A,n){
    	merge_sort_c(A,0,n-1)
    }
    
    //递归调用函数
    merge_sort_c(A,p,r){
    	//递归终止条件
    	if p >= n then return
    	
    	// 取p到r得到中间位置q
    	q = (p+r) /2
    	// 分治递归
    	merge_sort_c(A,p,q)
    	merge_sort_c(A,q+1,r)
    	// 将A[p...q]和A[q+1,r]合并为A[p...r]
    	merge(A[p...r],A[p...q],A[q+1,r])
    }

    你可能已经发现了,merge(A[p...r],A[p...q],A[q+1,r])这个函数的作用就是,将已经有序的A[p...q]和A[q+1,r]合并成一个有序的数组,并且放入A[p...r]。那这个过程具体该如何做呢?

    如图所示,我们申请一个临时数组tmp,大小与A[p...r]相同。我们用两个游标i和j,分别指向A[p...q]和A[q+1,r]的第一个元素。比较这两个元素A[i]和A[j],如果A[i]<=A[j],我们就把A[i]放入临时数组tmp,并且i后移一位,否则将A[j]放入到数组tmp,j后移一位。

    继续上诉比较过程,直到其中一个子数组中的所有数据都放入临时数组中,再把另一个数组中的数据依次加入到临时数组的末尾,这个时候,临时数组中存储的就是两个子数合并之后的结果了。最后再把临时数组tmp中的数据拷贝到原始组A[p...r]中。

    cba9bf16251aa025c35ab9a1ea80c2fa.png

    我们把merge()函数写成伪代码,就是下面这样:

    merge(A[p...r],A[p...q],A[q+1,r]){
    	//初始化变量i,j,k
    	var i:=p,j:=q+1,k:=0 
    	//申请一个大小跟A[p...r]一样的临时数组
    	var tmp:=new array[0...r-p] 
    	while i<q AND j<r do {
    		if A[i] < A[J]{
    			tmp[k++]  = A[i++] // i++等于i:=i+1
    		}
    		else
    			{
    				tmp[k++] =A[j++]
    			}
    	}
    	// 判断哪个子数组中有剩余的数据
    	var start := i,end :=q
    		if j<=r then start :j,end:=r
    			
    	// 将剩余的数据拷贝到临时数组tmp
    	while start <= end do{
    		tmp[k++] = A[start++]
    	}
    	
    	// 将tmp中的数组拷贝回A[p...r]
    	for i:0 to r-p do {
    		A[p+i] = tmp[i]
    	}
    }
    

    你还记得之前讲过的利用哨兵简化编程的处理技巧吗?merge()合并函数如果借助哨兵,代码就会简洁很多,这个问题留给你思考。

    归并排序的性能分析

    这样跟着我一步一步分析,归并排序是不是没那么难啦?还记得上节课我们分析排序算法的三个问题?接下来,我们来看归并排序的三个问题。

    第一,归并排序是稳定的排序算法吗?

    结合我前面画的那张图和归并排序的伪代码,你应该该能发现,归并排序稳不稳定关键要看merge()函数,也就是两个有序子数组合并成一个有序数组的那部分代码。

    在合并的过程中,如果A[p...q]和A[q+1...r]之间有值相同的元素,那我们可以像伪代码中那样,先把A[p...q]中的元素放入tmp数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定的排序算法。

    第二,归并排序的时间复杂度是多少?

    归并排序涉及递归,时间复杂度的分析稍微有点复杂。我们正好借此机会来学习一下,如何分析递归代码的时间复杂度。

    在递归那一节我们讲过,递归的使用场景是,一个问题a可以分解为多个子问题b,c,那求解问题a就可以分解为求解问题b,c。问题b,c解决之后,我们再把b,c的结果合并成a的结果。

    如果我们定义求解问题a的时间是T(a),求解问题b,c的时间复杂度是T(b)和T(c),那我们就可以得到这样的递推关系式:

    T(a) = T(b) +T(c) + K

    其中K等于将两个子问题b,c的结果合并成问题a的结果所消耗的时间。

    从刚刚的分析,我们可以得到一个重要的结论:不仅递归求解的问题可以写出递推公式,递归代码的时间复杂度也可以写成递推公式。

    套用这个公式,我们来分析一下归并排序的时间复杂度。

    我们假设对n个元素进行归并排序需要的时间是T(n),那分解成两个子数组排序的时间都是T(n/2)。我们知道,merge()函数合并两个有序子数组的时间复杂度是O(n)。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是:

    T(1) = C; n=1时,只需要常量级的执行时间,所以表示为C。
    T(n) = 2*T(n/2) + n; n>1

    通过这个公式,如何来求解T(n)呢?还不够直观?那我们再进一步分解一下计算过程。

    T(n) = 2*T(n/2) + n
         = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) +2*n
         = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) +3*n
         = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) +4*n
    ......
         =2^k *T(n/2^k) + k * n
    ......

    通过这样一步一步分解推导,我们可以得到T(n) = 2^k *T(n/2^k) + k * n。当T(n/2^k) = T(1)时,也就是n/2^k =1 ,我们得到k = log2n,我们将k值代入上面的公式,得到T(n) = Cn +nlog2n。如果我们用大O标记法来表示的话,T(n) 就等于O(nlogn)。所以归并排序的时间复杂度是O(nlogn)。

    从我们的原理分析伪代码可以看出,归并排序执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况,最坏情况,还是平均情况,时间复杂度是O(nlogn)。

    第三,归并排序的空间复杂度是多少?

    归并排序的时间复杂度任何情况下都是O(nlogn),看起来非常优秀。(待会你会发现,即便时候快速排序,最坏情况下,时间复杂度也是O(n^2)。)但是,归并排序并没有像快排那样,应用广泛,这个是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。

    这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你,归并排序的空间复杂度到底是多少呢?是O(n),还是O(nlogn),应该如何分析呢?

    如果我们继续按照分析递归时间复杂度的方法,通过递归公式来求解,那整个归并过程需要的空间复杂度就是O(nlogn)。不过,类似分析时间复杂度那样来分析空间复杂度,这个思路对吗?

    实际上,递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点,那就是,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小,所以空间复杂度是O(n)。

    快速排序的原理

    我们再来看快速排序算法(Quicksort),我们习惯性把它简称为“快排”。快排利用的也是分治思想。咋看起来,它有点像归并排序,但是思路其实完全不一样。我们待会会讲两者的区别。现在,我们先来看下快排的核心思想。

    快排的思想是这样的:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)。

    我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

    8c8b9537646799ea890fdd88766d5a67.png

    根据分治,递归的处理思想,我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩小为1,就说明所有的数据都有序了。

    如果我们用递归公式来将上面的过程写出来的话,就是这样:

    递推公式:
    quick_sort(p...r) = quick_sort(p...q-1) +quick_sort(q+1...r)
    
    终止条件:
    p >= r

    我将递归公式转化成递归代码。跟归并排序一样,我还是用伪代码来实现,你可以翻译成你熟悉的任何语言。

    //快速排序,A是数组,n表示数组的大小
    quick_sort(A,n){
    	quick_sort_c(A,0,n-1)
    }
    
    //快速排序递归函数,p,r为下标
    quick_sort_c(A,p,r){
    	if q >= r then return
    		
    		q = partition(A,p,r) //获取分区点
    		quick_sort_c(A,p,q-1)
    		quick_sort_c(A,q+1,r)
    }

    归并排序中有一个merge()合并函数,我们这里有一个partition()分区函数。partition分区函数实际上我们前面已经讲过了,就是随机选择一个元素作为pivot(一般情况下,可以选择p到r的最后一个元素),然后对A[p...r]分区,函数返回pivot的下标。

    如果我们不考虑空间消耗的话,partition分区函数可以写得非常简单。我们申请两个临时数组X和Y,遍历A[p...r],将小于pivot的元素都拷贝到临时数组X,将大于pivot的元素都拷贝到临时数组Y,最后再将数据X和数组Y中数据顺序拷贝到A[p...r]。

    d13bf44c975dc4dfd972ca11daa9f0bd.png

    但是,如果按照这种思路实现的话,partition()函数就需要很多额外的内存空间,所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法,那它的空间复杂度得是O(1),那partition分区函数就不能占用太多额外内存空间,我们就需要在A[p...r]的原地完成分区操作。

    原地分区函数的实现思路非常巧妙,我们写出了外代码,我们一起来看一下。

    partition(A,p,r){
    	pivot = A[r]
    	i:=p
    	for j:=p to r-1 do{
    		if A[j] < pivot {
    			swap A[i] with A[j]
    			i:=i+1
    		}
    	}
    	swap A[i] with A[i]
    	return i
    }

    这里的处理有点类似选择排序。我们通过游标i把A[p...r-1]分成两部分。A[p...i-1]的元素都是小于pivot的,我们暂且叫它“已处理区间”,A[i...r-1]是“未处理区间”。我们每次都从未处理的区间A[i,r-1]中取一个元素A[j],与pivot对比,如果小于pivot,则将其加入到已处理区间的尾部,也就是A[i]的位置。

    数组的插入操作还记得吗?在数据某个位置插入元素,需要搬移数据,非常耗时。当时我们也讲了一个处理技巧,就是交换,在O(1)的时间复杂度内完成插入操作。我们也是借助这个思想,只需要将A[i]与A[j]交换,就可以在O(1)时间复杂度内将A[j]放到下标为i的位置。

    文字不如图直观,所以我画了一张图来展示分区的整个过程。

    2a54902ce5a3aee81c2ca3df25fc6537.png

    因为分区的过程涉及交换操作,如果数组中有两个相同的元素,比如序列6,8,7,6,3,5,9,4在经过第一次分区操作之后,两个6的相对先后顺序就会改变。所以快速排序并不是一个稳定的排序。

    到此,快速排序的原理你应该也掌握了。现在,我再来看另外一个问题:快排和归并用的都是分治思想,递推公式和递归代码也非常相识,那他们的区别在哪里呢?

    64ffcc02a99dd9aa4ffb8c472db42e9d.png

    可以发现,归并排序的处理过程是由上到下的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题。归并排序虽然是稳定的,时间复杂度为O(nlogn)的排序算法,但是它是非原地排序算法。我们前面讲过,归并之所以是非原地排序,主要原因是合并函数无法原地执行。快速排序通过涉及巧妙的原地分区函数,可以实现原地排序,解决了归并排序占用太多内存的问题。

    快速排序的性能分析

    现在,我们来分析一下快速排序的性能。我在讲解快排的实现原理的时候,已经分析了稳定性和空间复杂度。快排是一种原地,不稳定的排序算法。现在,我们集中精力来看快排的时间复杂度。

    快排也是用递归实现的。对于递归代码的时间复杂度,我前面总结的公式,这里也还是适用的。如果每次分区操作,都能正好把数组分词大小接近相等的两个小区间,那快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是O(nlogn)。

    T(1) =C; n=1时,只需要常量级的执行时间,所以表示为C
    T(n) = 2*T(n/2) + n; n > 1

    但是,公式成立的前提是每次分区操作,我们选择的pivot都很合适,正好能讲大区间对等地一分为二。但实际上这种情况时候很难实现的。

    我举一个比较极端的例子。如果数组中的数据原来已经是有序的了,比如1,3,5,6,8。如果我们每次选择最后一个元素作为pivot,那每次分区得到的两个区间都是不均等的。我们需要进行大约n次分区操作,才能完成快排的整个过程。每次分区我们平均要扫描大n/2个元素,这种情况下,快排的时间复杂度就从O(nlogn)退化成了O(n^2)。

    我们刚刚讲了两个极端情况下的时间复杂度,一个是分区极其均衡,一个是分区极其不均衡。他们分别对应的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均情况时间复杂度是多少呢?

    我们假设每次分区操作都将区间分为大小为9:1的两个小区间。我们继续套用递归时间复杂度的递推公式,就会编程这样:

    T(1) =C; n=1时,只需要常量级的执行时间,所以表示为C
    T(n) = T(n/10) + T(9*n/10)+ n; n > 1

    这个公式的递推求解的过程非常复杂,虽然可以求解,但我不推荐用这种方法。实际上,递归的时间复杂度的求解方法除了递归公式之外,还有递归树,在树那一节我再讲,这里暂时不说。我这里直接给你结论:T(n)在大部分情况下的时间复杂度都可以做到O(nlogn),只有在极端情况下,才会退化到O(n^2)。而且,我们也有很多方法将这个概率降到很低,如果来做?我们后面章节再讲。

    解答开篇

    快排核心思想就是分治和分区,我们可以利用分区的思想,来解答开篇的问题:O(n)时间复杂度内求无序数组中的第K大元素。比如,4,2,5,12,2这样一组数据,第3大元素就是4。

    我们选择数据区间A[0...n-1]的最后一个元素A[n-1]作为pivot,对数组A[0...n-1]原地分区,这样数组就分成了三部分,A[0...p-1],A[p],A[p+1,...n-1]。

    如果p+1 =K,那A[p]就是要求解的元素;如果K>p+1,说明第K大元素出现在A[p+1...n-1]区间,我们再按照上面的思路递归地在A[p+1...n-1]这个区间内查找。同理,如果K<p+1,那我们就在A[0...p-1]区间查找。

    3df9f4f4f47006d711b5798488298395.png

    我们再来看,为什么上述解决思路的时间复杂度是O(n)?

    第一次分区查找,我们需要对大小为n的数组执行分区操作,需要遍历n个元素。第二次分区查找,我们只需要对大小为n/2的数组执行分区操作,需要遍历n/2个元素。依次类推,分区遍历元素的个数分别为n/2,n/4,n/8,n/16......直到区间缩小为1。

    如果我们把每次分区遍历的元素个数加起来,就是n+n/2 +n/4+n/8+...+1。这是一个等比数列求和,最后的和等于2n-1。所以,上述解决思路的时间复杂度就为O(n)。

    你可能会说,我有一个很笨的办法,每次去数组中的最小值,将其移动到数组的最前面,然后在剩下的数组中继续找最小值,以此类推,执行K次,找到的数组不就是第K大元素了吗?

    不过,时间复杂度就并不是O(n)了,而是O(K*n)。你可能会说,时间复杂度前面的系数不是可以忽略吗?O(K * n)不就是等于O(n)吗?

    这个可不能这么简单地划等号。当K是比较小的常数时,比如1,2,那最好时间复杂度确实是O(n);但当K等于n/2或者n时,这种最坏情况的时间复杂度就是O(n^2)了。

    内容小结

    归并排序和快速排序是两种稍微复杂的排序算法,他们用的都是分治的思想,代码都通过递归来实现,过程非常相识。理解归并排序的重点是理解递推公式和merge()合并函数。同理,理解快排的重点也是理解递推公式,还有partition()分区函数。

    归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是O(n)。正因为此,它也没有快排应用广泛。

    快速排序算法虽然最坏情况下的时间复杂度是O(n^2),但是平均情况下时间复杂度都是O(nlogn)。不仅如此,快速排序算法时间复杂度退化到O(n^2)的概率非常小,我们可以通过合理地选择pivot来避免这种情况。

    参考文献

    王争老师 《数据结构与算法之美》

    展开全文
  • Vector 删除元素

    千次阅读 2014-07-21 08:47:15
    数据结构上机测试1:顺序表的应用 ...二行依次输入顺序表初始存放的n个元素值。 输出 一行输出完成多余元素删除以后顺序表的元素个数; 二行依次输出完成删除后的顺序表元素。 示例输入 12 5

    数据结构上机测试1:顺序表的应用

    Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^

    题目描述

    在长度为n(n<1000)的顺序表中可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只能有一个)。

    输入

    第一行输入表的长度n;
    第二行依次输入顺序表初始存放的n个元素值。

    输出

    第一行输出完成多余元素删除以后顺序表的元素个数;
    第二行依次输出完成删除后的顺序表元素。

    示例输入

    12
    5 2 5 3 3 4 2 5 7 5 4 3

    示例输出

    5
    5 2 3 4 7

    提示

    用尽可能少的时间和辅助存储空间。
    我自以为自己会用vector了 没想到删除元素也有不同(和list相比,以前做过list的删除元素)
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <cstdio>
    #include <cctype>
    #include <cmath>
    #include <vector>
    using  namespace std;
    int main()
    {
      int n,k,x;
      vector <int> s;
      vector <int>::iterator i,j;
      cin>>n;
      for(k=0;k<n;k++)
      {
      	cin>>x;
      	s.push_back(x);
      }
      int flag;
      for(i=s.begin();i!=s.end();)
      {
      	flag=1;
    	for(j=s.begin();j!=i;j++)
      	 if(*i==*j)
    	 {
    	 	flag=0;
    	 	i=s.erase(i);//与list删除元素不同
    	 	break;
    	 }
    	 if(flag)
    		i++;
      }
      cout<<s.size()<<endl;
    	for(k=0;k<s.size();k++)
    		if(k!=s.size()-1)
    		cout<<s[k]<<" ";
    	    else
    		cout<<s[k]<<endl;
      return 0;
    }


    展开全文
  • 给定一链表,删除链表的倒数 n 节点,并且返回链表的头结点。 示例: 给定一链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数节点后,链表变为 1->2->3->5. 说明: 给定的 n ...

    题目:

    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
    
    示例:
    
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    说明:
    
    给定的 n 保证是有效的。
    
    进阶:
    
    你能尝试使用一趟扫描实现吗?
    

    思路:

    1. 方法一: 使用vector记录每一个位置元素的指针
      遍历一次后,从vector中直接找到这个元素进行删除;

    2. 方法二:使用双指针:
      初始化两个指针的位置相间为 N个元素,当前面的元素到达终点,前面的元素自然就是倒数第N个元素;

    代码1:(方法一:)

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            vector<ListNode*> pvec;
            ListNode* p = head;
            while(p)
            {
                pvec.push_back(p);
                p = p->next;
            }
            
            ListNode* q = pvec[pvec.size() - n];
            if(q == head){
                head = head->next;
                return head;
            }
            else {
                q = pvec[pvec.size() - n - 1];
                q->next = q->next->next;
            }
            return head;       
        }
    };
    

    方法二:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            
    
            ListNode* pre_head = new ListNode(0);
            pre_head ->next = head;
            ListNode* p = pre_head , *pre = pre_head;
            for(int i = 0;i < n; i++)	// 先将p移动n个位置
                p = p->next;
    		// 开始移动两个指针;停下时,pre指向欲删除的前一个元素;
            while(p->next)
            {
                p = p->next;
                pre = pre->next;
            }
    
            ListNode* to_del = pre->next;
    
            pre->next = to_del->next;
            
            head = pre_head->next;
            delete(pre_head);
            delete(to_del);
    
            return head;
    
    
    
        }
    };
    
    展开全文
  • 完成数组元素的移动功能:假设数组有n个元素,输入一个数x,把数组的x个位置的元素删除了,后面的元素依次前进一个位置。 重复若干次这样的删除,得到最后的结果。 输入格式: 一行包括一个整数n(1<=n<=...

    7-5 数组元素的删除(5 分)

    完成数组元素的移动功能:假设数组有n个元素,输入一个数x,把数组的第x个位置的元素删除了,后面的元素依次前进一个位置。 重复若干次这样的删除,得到最后的结果。
    输入格式:

    第一行包括一个整数n(1<=n<=100),表示数组元素的个数。 第二行输入n个数组元素,均为整数,用空格隔开。 第三行输入一个数k(1<=k<=100),表示要进行k次删除。 接下来k行,每行一个数x,表示要删除第x个元素。
    输出格式:

    输出经过k次删除后的数组,每两个元素之间用空格隔开。
    输入样例:

    10
    1 2 3 4 5 6 7 8 9 10
    4
    3
    2
    4
    6

    输出样例:

    1 4 5 7 8 10

    思路
    用vector 保存数据 然后每次删除 用 erase 就行了

    AC代码

    #include <cstdio>
    #include <cstring>
    #include <ctype.h>
    #include <cstdlib>
    #include <cmath>
    #include <climits>
    #include <ctime>
    #include <iostream>
    #include <algorithm>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <map>
    #include <stack>
    #include <set>
    #include <numeric>
    #include <sstream>
    #include <iomanip>
    #include <limits>
    
    #define CLR(a) memset(a, 0, sizeof(a))
    
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    typedef unsigned long long ull;
    typedef pair <int, int> pii;
    typedef pair <ll, ll> pll;
    typedef pair<string, int> psi;
    typedef pair<string, string> pss;
    
    const double PI = 3.14159265358979323846264338327;
    const double E = exp(1);
    const double eps = 1e-6;
    
    const int INF = 0x3f3f3f3f;
    const int maxn = 1e6 + 5;
    const int MOD = 1e9 + 7;
    
    int main()
    {
        int n;
        cin >> n;
        vector <int> v;
        int num;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &num);
            v.push_back(num);
        }
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &num);
            v.erase(v.begin() + num - 1);
        }
        vector <int>::iterator it;
        for (it = v.begin(); it != v.end(); it++)
        {
            if (it != v.begin())
                printf(" ");
            cout << *it;
        }
        cout << endl;
    }

    转载于:https://www.cnblogs.com/Dup4/p/9433225.html

    展开全文
  • 中保存了m个ID,这时要删除第n个ID。 当然,遍历是一个方法;即vector::itertor it = vecID.begin(); 然后++it n次。 更好的方法是:vector::itertor it = vecID.begin() + n; vector的迭代器直接支持...
  • PTA - 数组元素删除 /移动 (vector容器)

    千次阅读 2019-06-20 20:53:43
    题目:完成数组元素的移动功能:假设数组有n个元素,输入一个数x,把数组的x个位置的元素先保存起来,然后把x+1到n的元素,依次往前移一位,最后将原来的x个位置的元素放在数组的最后。 重复若干次这样的移动,...
  • 多趟扫描也不好实现吧难道要一个个从尾元素开始逼近倒数123…k个元素吗 按顺序push进vector,取前面的元素改一下next指针就完了,如果要删除的是头元素就直接返回next。不知道这道题为啥能成中等(也可能是这题目...
  • C++ STL中 Vector的基本用法一维vector创建一维vectorvector<int> nums;//不指定长度vector<int> nums(n);...//直接赋值给i位置删除元素nums.resize(nums.size-i); //直接将数组...
  • n个元素围成一圈,每次删除第m个元素,求最后一个被删除的元素。#include #include "list" using namespace std; //使用list而非vector int findLast(int m,int n){ if(m||n){ return -1; } list<int> v;
  • 一行输入一整数 N,代表操作的总数 接下来的 N 行中, i 行包含两整数,分别为操作码 p 和操作数 k 操作码 p 定义如下: 0: 将号码 k 添加到记录中(忽略重复) 1: 将号码 k 从记录中删除 2: 宣布记录中 k...
  • vector容器的一问题

    2020-04-10 15:16:41
    这是我改写的一个代码,想通过循环删除vector容器中的个元素,把开头那六行删掉,把剩下从-9999开始的所有数字存到二维数组。方便后面计算,但是我在运行时提示如下错误 ``` void _Tidy() noexcept { // ...
  • vector用法

    千次阅读 2018-06-01 16:38:20
    一维vector创建一维vectorvector&lt;int&gt; nums; //不指定长度 vector&lt;int&gt; nums(n); // 指定长度为n 12添加元素nums.... //直接赋值给i位置12删除元素nums.resize(nums.size-i); ...
  • 时间复杂度分析:构建最大堆:O(n),删除k:O(klogn)。 首先记录一版调用api的代码 #include <iostream> #include <string> #include <set> #include <cmath> #include <vector&...
  • 返回个元素的引用; //下面两个操作只适用于vector和deque容器 c[n];返回下标为n的元素的引用; c.at(n);返回下标为n的元素的引用; //在调用front和back函数之前或者在对begin和end返回的迭代器进行解引用...
  • vector实现约瑟夫

    2017-12-14 15:06:29
    /* 1. 读入优化 的 初识、 约瑟夫实现 vector模拟实现 ... for遍历将 n-1 个元素 在容器中删除 t个元素 a.erase(a.begin()+t); 最后容器中的最后一个元素就是活下来的人 */ #include #include #include #include #i
  • vector的高级用法

    千次阅读 2015-04-17 16:58:16
    这里主要介绍vector的元素访问方法,...最后一个元素的索引下标为size()-1,即第n个元素的下标为n-1。可以直接访问vector型容器中元素的操作方法主要包括:at(),[],front(),back()。 其中,c.at(index)函数返回值
  • C++ STL中 Vector的基本用法一维vector创建一维vectorvector<int> nums;//不指定长度vector<int> nums(n);...//直接赋值给i位置删除元素nums.resize(nums.size-i); //直接将数组...
  • 流程如下:数组内容堆化(因为是查找K大,所以使用大根堆)、依次取出并删除堆的根节点、将剩余元素堆化、取到K即为目标元素。 二、代码实现 #include <iostream> #include <vector> using ...
  • C++ vector用法初记

    2021-03-15 20:28:52
    一维vector创建一维vector: 1. vector nums;//不指定长度 2. vector nums(n); // 指定长度为n 添加元素 1. nums.push_back(1);//直接从数组末端添加 ...//删掉最后一个元素 数组遍历 1. for(int i = 0; i <
  • vector的基本操作

    2021-04-02 08:43:09
    myvector.push _back(<T>) 可以往vector中添加元素,当容器满了之后,容器会自动动态扩容,会重新建一个vector容器,然后将原vector容器的内容拷贝至新容器中。在动态扩容时会多扩充一些...//删除容器中的第n.
  • c++中的顺序容器有vector,deque,queue,list,stack,priority_queue等 访问顺序容器内元素的...返回容器c的个元素的引用。如果c为空,操作未定义。 c[n] 返回下标为n的元素的引用 如果n=c.size(),该操作未定义
  • Vector创建数组的方法: 一维vector 创建一维vectorvector<int> nums;//不指定长度vector<int> nums(n); // 指定长度为n ...//直接赋值给i位置 1 2 删除元素 nums.resize(nums.s...
  • C++:vector<int>

    2019-04-02 14:34:26
    一维vector 创建一维vectorvector<int> nums;//不指定长度 vector<int> nums(n);...//直接赋值给i位置 删除元素 nums.resize(nums.size-i); //直接将数组长度减小,某种方式上...
  • 【C++】vector常用操作

    2018-08-02 11:50:42
    vector常用操作 v.empty() 如果v中不含任何元素,返回真;否则返回假 v.size() 返回v中元素的个数 v.push_back(t) 向v的尾端添加一值为t的元素 v.pop_back() ... 返回v第n...
  • 2.vec.resize(n)//调整容器中元素个数为n,当n小于当前容器大小时,只保留前n个元素。 vec.resize(n,a)//当n大于当前容器大小时,用指定元素a补在后面,若未指定则使用默认构造函数。 3.vec.empty()//判断容器中元素...
  • 八周 标准模板库STL(一) 1.string类 ...根据下标访问时间复杂度是O(1),常量时间,在尾部添加、删除元素的时间复杂度是O(1),在中间添加、删除元素的时间复杂度是O(n)。以下是几关于vector构造...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 122
精华内容 48
热门标签
关键字:

vector删除第n个元素