Java教程

每日一算法(3)

本文主要是介绍每日一算法(3),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

每日算法篇-22王道数据结构

“之前没有打算写博客来记写下每天练习的算法,都是在自己的小本本上,但是突然有一天,发现王道答案的解释看不懂,所以想把自己的对算法理解记录下来,也不是为了让谁看到。由于时间很紧,前两天都安排在了晚上,陪对象打电话的时间,但是效率很低下,所以自己要养成一个好习惯——只做一件事,这也是是在小红书学到的高效方法,就是哪怕发呆,都要认真的发呆。”——努力成为程序员的耿耿(2021/10/23)

题目

对长度为n的顺序表L,编写一个时间复杂度为 O(n),空间复杂度为 O(1)的算法,该算法删除线性表中所有值为x的数据元素。---------22王道数据结构第二章综合应用题(2.3)
思考: 首先看到的是空间复杂度为O(1),所以说放弃再建一个顺序表,把不是x的值一个一个加入的想法。其次复杂度为O(n),标明了算法中最多能有一个循环就可以解决问题。设置一个标记位flag,从头遍历整个顺序表,将每个值进行与x比较,如果相等,标记位加一,将后边的数赋值给当前遍历中(i-flat)的值,如果不等同样把值放到前面,用覆盖达到删除的效果。最后释放顺序表后边flat长度的数释放空间即可。

bool del_x(Sqlist &L,ElemType x){
	if (L.length==0)
		return false;
	int flag=0
	for(int i=0;i<L.length;i++){
		if(L.data[i]==x)
			flag+=1;
		else
			L.data[i-flag]=L.data[i];
	}
	L.length-=flag
	return ture;
}

这道题如果你们看书的话,答案应该是两种算法,另一种是用flag记录不是x的个数,思路是一样的,就像极限中趋于0有趋于0+,趋于0-,结果都是趋于0,只是路径不一样而已。
之后几天的算法应该都会是蓝桥往年例题,更为综合一点,最近为蓝桥校选赛做一些准备,等结束了,继续从顺序表学起。

这篇关于每日一算法(3)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!