前十天把Linux系统管理和Shell编程的基本功过了一遍从虚拟机安装到用户权限管理从文件操作到结构化命令总算是能写一些像样的脚本了。但课程推进到第三周突然换了个方向从Shell脚本跳到了数据结构与算法。说实话一开始有点懵感觉Linux还没学透怎么就开始搞算法了。后来理解了这套小学期的设计思路其实是先搭环境、再练命令、最后用编程来解决实际问题前面学的Shell脚本算是给后面打基础的过渡。这周的主要内容是数据结构概述、数组基础知识、二分查找和移除元素对应着LeetCode上的704题和27题。今天先把这块的内容整理出来。先说说数据结构是什么。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的而是有着某种关系这种关系构成了某种结构。Pascal之父尼古拉斯·沃斯有一个著名公式程序 算法 数据结构。这个公式把程序设计的两个核心要素说得非常清楚数据结构和算法缺一不可数据结构是组织数据的方式算法是处理数据的方法。数组是最基本的数据结构。数组是n个相同类型数据元素构成的有限序列逻辑表示为A(a1, a2, ..., an)。数组有一个很重要的特性叫随机访问一旦a1的存储地址确定并假设每个数据元素占用k个存储单元则任一数据元素ai的存储地址就可由公式LOC(ai)LOC(a1)(i-1)*k直接计算出来。这意味着数组中任一数据元素都可以直接存取不需要从头遍历去找所以数组是一种随机存储结构。在Python中数组对应的是列表类型列表的基本形式是一个方括号内以逗号分隔的若干值而且Python的列表不需要所有值都是相同类型这一点比C语言灵活不少。前面学的顺序查找其实就是遍历数组逐个比较直到找到目标值。我在脚本里用循环遍历数组元素的时候本质上就是顺序查找的思路。Python代码实现起来很直观定义一个函数sq_search(R, n, k)从表头开始逐个比较找到就返回逻辑序号找不到就返回0。这种方法在数据量小的时候没什么问题但如果数据量大了效率就不够看了。二分查找就不一样了它是一种效率较高的查找方法但前提是顺序表中的元素必须是有序的。假设有序顺序表是递增有序的基本思路是确定当前查找区间的中点位置mid然后将待查的k值与R[mid]比较。如果相等就找到了如果R[mid]大于k说明k在左子表新的查找区间是low到mid-1如果R[mid]小于k说明k在右子表新的查找区间是mid1到high。每次查找都让区间缩小一半所以效率比顺序查找高很多。课件里用有序序列2,4,7,9,10,14,18,26,32,40演示了查找7的过程。第一次mid是5R[5]14大于7所以去左子表第二次mid是2R[2]7找到了总共只比较了两次就找到了目标。用Python实现二分查找有两种常见的区间定义方式。左闭右闭的写法是定义target在[left, right]区间里while循环条件是left right因为left等于right时区间里还有一个元素。当nums[middle]大于target时right middle - 1因为middle已经检查过了不在新的区间里。左闭右开的写法是定义target在[left, right)区间里while循环条件是left right因为left等于right时区间是空的。当nums[middle]大于target时right middle因为右开区间不包含right。两种写法边界条件稍微不同但核心思想是一样的。移除元素这道题要求原地修改输入数组不使用额外的数组空间只使用O(1)的额外空间。暴力解法的思路是遍历数组找到等于目标值的元素然后把后面的元素依次向前平移一位数组长度减一。但这种方法时间复杂度是O(n²)因为每次删除都要移动后面所有的元素。快慢指针法更优雅一些快指针遍历整个数组慢指针用来收集不等于目标值的元素。如果快指针指向的值不等于目标值就把它赋值给慢指针指向的位置然后慢指针加一。这样一趟遍历下来所有不等于目标值的元素都被挪到了数组前面慢指针的值就是新数组的长度。时间复杂度O(n)比暴力解法高效不少。把数据结构这块和之前学的Shell脚本串起来看shell脚本里的数组本质上就是数据结构里的数组概念在具体编程环境中的体现。之前用循环遍历数组、用if判断条件、用变量存储数据其实都是在应用数据结构和算法的思想。二分查找的核心思想是每次排除一半的数据这种分治策略在Shell脚本里也可以实现只不过实现起来不如Python方便。接下来的学习要进入Python编程实战了数据结构与算法这套体系是计算机专业的核心基础打好基础后面学什么都更顺畅。希望这篇文章能给正在入门数据结构的同学一些参考有问题欢迎来交流。
前十天把Linux系统管理和Shell编程的基本功过了一遍从虚拟机安装到用户权限管理从文件操作到结构化命令总算是能写一些像样的脚本了。但课程推进到第三周突然换了个方向从Shell脚本跳到了数据结构与算法。说实话一开始有点懵感觉Linux还没学透怎么就开始搞算法了。后来理解了这套小学期的设计思路其实是先搭环境、再练命令、最后用编程来解决实际问题前面学的Shell脚本算是给后面打基础的过渡。这周的主要内容是数据结构概述、数组基础知识、二分查找和移除元素对应着LeetCode上的704题和27题。今天先把这块的内容整理出来。先说说数据结构是什么。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的而是有着某种关系这种关系构成了某种结构。Pascal之父尼古拉斯·沃斯有一个著名公式程序 算法 数据结构。这个公式把程序设计的两个核心要素说得非常清楚数据结构和算法缺一不可数据结构是组织数据的方式算法是处理数据的方法。数组是最基本的数据结构。数组是n个相同类型数据元素构成的有限序列逻辑表示为A(a1, a2, ..., an)。数组有一个很重要的特性叫随机访问一旦a1的存储地址确定并假设每个数据元素占用k个存储单元则任一数据元素ai的存储地址就可由公式LOC(ai)LOC(a1)(i-1)*k直接计算出来。这意味着数组中任一数据元素都可以直接存取不需要从头遍历去找所以数组是一种随机存储结构。在Python中数组对应的是列表类型列表的基本形式是一个方括号内以逗号分隔的若干值而且Python的列表不需要所有值都是相同类型这一点比C语言灵活不少。前面学的顺序查找其实就是遍历数组逐个比较直到找到目标值。我在脚本里用循环遍历数组元素的时候本质上就是顺序查找的思路。Python代码实现起来很直观定义一个函数sq_search(R, n, k)从表头开始逐个比较找到就返回逻辑序号找不到就返回0。这种方法在数据量小的时候没什么问题但如果数据量大了效率就不够看了。二分查找就不一样了它是一种效率较高的查找方法但前提是顺序表中的元素必须是有序的。假设有序顺序表是递增有序的基本思路是确定当前查找区间的中点位置mid然后将待查的k值与R[mid]比较。如果相等就找到了如果R[mid]大于k说明k在左子表新的查找区间是low到mid-1如果R[mid]小于k说明k在右子表新的查找区间是mid1到high。每次查找都让区间缩小一半所以效率比顺序查找高很多。课件里用有序序列2,4,7,9,10,14,18,26,32,40演示了查找7的过程。第一次mid是5R[5]14大于7所以去左子表第二次mid是2R[2]7找到了总共只比较了两次就找到了目标。用Python实现二分查找有两种常见的区间定义方式。左闭右闭的写法是定义target在[left, right]区间里while循环条件是left right因为left等于right时区间里还有一个元素。当nums[middle]大于target时right middle - 1因为middle已经检查过了不在新的区间里。左闭右开的写法是定义target在[left, right)区间里while循环条件是left right因为left等于right时区间是空的。当nums[middle]大于target时right middle因为右开区间不包含right。两种写法边界条件稍微不同但核心思想是一样的。移除元素这道题要求原地修改输入数组不使用额外的数组空间只使用O(1)的额外空间。暴力解法的思路是遍历数组找到等于目标值的元素然后把后面的元素依次向前平移一位数组长度减一。但这种方法时间复杂度是O(n²)因为每次删除都要移动后面所有的元素。快慢指针法更优雅一些快指针遍历整个数组慢指针用来收集不等于目标值的元素。如果快指针指向的值不等于目标值就把它赋值给慢指针指向的位置然后慢指针加一。这样一趟遍历下来所有不等于目标值的元素都被挪到了数组前面慢指针的值就是新数组的长度。时间复杂度O(n)比暴力解法高效不少。把数据结构这块和之前学的Shell脚本串起来看shell脚本里的数组本质上就是数据结构里的数组概念在具体编程环境中的体现。之前用循环遍历数组、用if判断条件、用变量存储数据其实都是在应用数据结构和算法的思想。二分查找的核心思想是每次排除一半的数据这种分治策略在Shell脚本里也可以实现只不过实现起来不如Python方便。接下来的学习要进入Python编程实战了数据结构与算法这套体系是计算机专业的核心基础打好基础后面学什么都更顺畅。希望这篇文章能给正在入门数据结构的同学一些参考有问题欢迎来交流。
