数据结构 给定一个集合，要从这个集合查询某个或者某些元素。常见的做法有： 直接遍历 从集合头到集合为挨个遍历，直到找到需要查找的元素或者已经全部遍历完成。很明显这个方法的时间复杂度是O(n)。随着集合的增大，查询耗时将会线性增加。 二分查找 基于有序数组的情况下，先拿目标元素与集合中间位置元素比较 …
标签: 数据结构
简单的链表直接反转 思路： 定义三个指针curr，pre, next分别指向当前节点，前序节点和后继节点。那么对于当前节点来说，要实现反转，就是将当前节点的后继指针指向它的前序节点即可。处理完当前节点，指针移动到下一个节点，继续执行上面操作。直到当前节点为空为止。 操作图示： <span …
核心思想 将数组分为两个子数组，其中一个子数组为有序数组，另一个为无序数组。然后从无序数组中取到最值元素，然后依次将这些最值元素追加到有序数组中。 实现代码 public void sort(int[] arr){ for(int i = 0; i < arr.length; i++) { …
核心思想 将数组分成两部分，一部分是有序数组，一部分是无序数组。每次从无序数组中拿出一个元素，将这个元素放置到有序数组中合适的位置。直到整个数组都有序为止。 代码实现 public void sort(int[] arr) { for(int i = 0; i < arr.length; …
思路 从数组中找一个基准元素，以基准元素将数组分成三部分： $$patition(n) = \begin{cases} x, & \text{x<baseEliment} \ baseEliment \ y & \text{y>baseEliment} \ …