程序员

归并排序

基本思想 核心思想是“分治法”。 将序列看成nge有序的子序列,每个序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列,然后再两两归并······这样重复下去,直到得到一个长度为n的有序序列,这种排序方法叫做2-路归并算法。依次类推,还有3-路归并排序等等。 如何有效的将两个有序序列…

程序员

lintcode第三十题 插入空间

给出一个无重叠的按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。插入区间[2, 5] 到 [[1,2], [5,9]],我们得到 [[1,9]]。插入区间[3, 4] 到 [[1,2], [5,9]],我们得到 [[1,…

程序员

堆排序

数据结构堆 是一颗完全二叉树。完全二叉树:设二叉树的深度为h,除了第h层以外,前面的每一层的节点数都达到最大,并且第h层的叶子都集中在最左边。 所有非终端(有叶子)节点的值均不小于(或不大于)其左、右孩子的值。前者叫大顶堆,后者叫小顶堆。 堆排序思想 利用堆数据结构的堆顶肯定是最大值(或最小值),则…

大数据

排序算法总结(一) 堆排序

1 时间复杂度对比 排序算法时间复杂度总结.png 本节我们只关注堆排序的时间复杂度.首先, 从上图我们可以看到,堆排序是不稳定的. 排序算法的稳定性: 对于一组数,如果相同元素的相对位置在排序前后保持一致,则该算法是稳定的,否则是不稳定的. 其次, 堆排序的时间复杂度都是O(nlogn), 空间复…

大数据

lintcode 第十七、十八题 子集和带重复数字的子集

第十七题是给定一个不含重复数字的集合,返回其子集;十八题是给定一个可能有重复数字的集合,返回其子集。先来说没有重复数字的情况首先把空集合加进去,然后在循环里面进行递归调用,在进行递归时,将i的值加1,就可以排除前面已经加进去的数字,这道题可以和十五十六题进行比较,都属于深度优先搜索。代码如下: cl…

大数据

lintcode第二十八题 搜索二维矩阵

lintcode的题号比较尴尬,十八题完了就直接成了二十八题,不知道是我没有找到还是它本来就是这样的。写出一个高效的算法来搜索 m × n矩阵中的值。这个矩阵具有以下特性:每行中的整数从左到右是排序的。每行的第一个数大于上一行的最后一个整数。这个数组简单的说就是从小到大依次排列,排满一行就换到下一行…

大数据

lintcode第十四题 二分查找

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。样例在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。典型的二分查找问题,考虑到数组中有重复的数字,…