6 涛爸

尚未进行身份认证

勿在浮沙筑高台

等级
TA的排名 4w+

S中最接近中位数的k个元素

在《算法导论》第3版习题习题9.3-7提到,设计一个O(n)时间的算法,对于一个给定的包含n个互异元素的集合S和一个正整数 k<=n,该算法能够确定S中最接近中位数的k个元素。步骤如下:1: select A数组得到其中位数nmid,其下标为imid2: 计算A中每个数到中位数的差值作为数组dis, 并拷贝到数组dis_copy3: select dis_copy数组得到第k...

2018-07-24 11:46:13

最坏情况为线性时间的选择算法

《算法导论》第3版9.3讲解了最坏情况为线性时间的选择算法步骤如下1: 将输入数组的n个元素划分为 n/5 组,每组5个元素,且至多只有一组由剩下的 n%5 个元素组成。2: 寻找 n/5 组中每一组的中位数:首先对每组元素(至多为5个)进行插入排序,然后确定每组有序元素的中位数。3: 对第2步中找出的 n/5 个中位数,递归调用 select 以找出其中位数 num(如果有偶数个...

2018-07-23 20:17:54

期望为线性时间的选择算法

《算法导论》第3版9.2提到了期望为线性时间的选择算法 randomized_select 算法是以第7章的快速排序算法为模型的。 与快速排序一样,我们仍然将输入数组进行递归划分。 但与快速排序不同的是,快速排序会递归处理划分的两边, 而 randomized_select 只处理划分的一边。数组 A[p..r] 被划分为两个子数组 A[p..q-1] 和 A[q+1..r] ...

2018-07-20 11:15:37

最小值和最大值

《算法导论》第3版9.1提到了如何查找最小值和最大值1:锦标赛排序:为了确定min/max,必须要做n-1次比较 完整源代码放于github2:将一对输入元素相互进行比较,然后把较小的与当前最小值比较,把较大的与当前最大值进行比较。 这样,对每两个元素共需3次比较,总的比较次数至多是3n/2代码如下struct node { int max; in...

2018-07-19 15:50:23

桶排序

《算法导论》第3版8.4描述了桶排序桶排序将[0,1)区间划分为n个相同大小的子区间,或称为桶。 然后,将n个输入数分别放到各个桶中。 为了得到输出结果,先对各个桶中的数进行排序,然后遍历每个桶, 按照次序把各个桶中的元素列出来即可。代码如下struct Node{ double value; Node *next;};void bucket_sort...

2018-07-18 18:06:41

基数排序

《算法导论》第3版8.3提到了基数排序基数排序(radix sort)是一种用在卡片排序机上的算法。 先按最低有效位进行排序,再按次低有效位进行排序,重复这一过程,直到对所有的d位数完全排好序。 为了使基数排序正确运行,一位数排序算法:计数排序必须是稳定的。代码如下void radix_sort(int A[], int B[], int d){ int *C =...

2018-07-18 11:14:59

计数排序

《算法导论》第3版8.2提到了计数排序计数排序假设输入n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数。 计数排序的基本思想是:对每一个输入元素x,确定小于x的元素个数。利用这一信息,就可以直接把x放到它在输出数组中的位置上了。但当有几个元素相同时,则不能把它们放在同一个输出位置上。 因此除了输入数组A[0..n-1],我们还需要两个数组:B[0..n-1]存放排序...

2018-07-18 11:11:07

快速排序

《算法导论》第3版7.1提出了快速排序的描述与归并排序一样,快速排序也使用了分治思想。下面是对一个典型的子数组A[p..r]进行快速排序的三步分治过程:分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素 都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中,计算下标q也是划分过程的一部...

2018-07-16 10:37:26

优先队列

《算法导论》第3版6.5讲解了优先队列优先队列(priority queue)是一种用来维护由一组元素构成的集合S的数据结构, 其中的每一个元素都有一个相关的值,称为关键字(key)。 一个最大优先队列支持以下操作:1) insert(S, x): 把元素x插入集合S中,这一操作等价于S=S∪{x}2) maximum(S): 返回S中具有最大键字的元素3) extract_m...

2018-07-15 17:50:24

堆排序

在《算法导论》第3版第6章讲解了堆排序算法1:初始时候,利用 build_max_heap 将输入数组 A[0..n-1] 建成最大堆 2:因为数组中的最大元素总在根结点 A[0] 中,把它与 A[n-1] 互换,从而让该元素放到正确的位置。 3:这时候,从堆中去掉结点 n-1(–heap_size),剩余的结点中,原来根的孩子结点仍然是最大堆,而新的根结点 可能会违背最大堆的性质。为了...

2018-07-06 19:06:23

LeetCode-053. Maximum Subarray

1. 题目Maximum Subarray 给定一个数组,找出其最大连续子序列和 2. 分析动态规划,先找出局部最优解,再从局部最优解中找出全局最优解3. 代码class Solution {public: int maxSubArray(vector<int>& nums)

2018-07-05 19:51:33

最大子数组问题

1. 暴力解法在《算法导论》第3版习题4.1-2提到,对最大子数组问题进行暴力求解 使用两个for循环即可,代码如下void maxSubArray(vector<int> &nums){ int len = nums.size(); if (len &amp

2018-07-02 19:37:10

LeetCode-067. Add Binary

1. 题目Add Binary 给定两个二进制字符串,返回它们的总和 (也是二进制字符串) 输入字符串都是非空的,只包含字符1或0。2. 分析从尾到头遍历字符串 每次取出1个字符,转为数字,若无字符则按0处理 定义进位carry,初始值为0 将三者加起来,对2取余即为当前位的数字,对2取商即为进位的值 注意return时候,carry千万不要遗漏,如果c...

2018-06-30 14:21:53

两个n位二进制整数相加

《算法导论》第3版习题2.1-4中提到把两个n位二进制整数加起来的问题,这两个整数分别存储在两个n元数组A和B中,这两个整数的和应按二进制形式存储在一个(n+1)元数组C中。可先将A、B数组反转,按位相加,定义进位carry,初始化为0,将三者加起来,对2取余即为当前位,对2取商即为当前进位,再将C数组反转一次即可得到想要的结果。void reverseArray(int A[], int...

2018-06-30 13:47:36

LeetCode-018. 4Sum

1. 题目4Sum 查找数组中和为0的4个数 解决方案集不能含有重复项2. 分析1:传统k-sum问题,先排序,再左右夹逼 时间复杂度O(n^3),空间复杂度O(1) 2:借助unordered_multimap(允许重复key)缓存两数之和 时间复杂度O(n^2),空间复杂度O(n^2) 注意内层循环是for(int j = i + 1; j &lt...

2018-06-29 20:30:50

LeetCode-016. 3Sum Closest

1. 题目3Sum Closest 求最接近target的三数之和 假定每个输入都只有一个解决方案2. 分析要保证三数和跟target差的绝对值最小 brute force时间复杂度为O(n^3) 优化的解法是先排序再左右夹逼 我们需要定义一个变量diff用来记录差的绝对值 先确定一个数,再滑动寻找另外两个数 每确定两个数,求出此三数之和 再算...

2018-06-28 20:16:57

LeetCode-015. 3Sum

1. 题目3Sum 在数组中找到和为0的三个数,结果不重复2. 分析本题是Two Sum的扩展,brute force时间复杂度为O(n^3) 但这里使用哈希表的解法并不合适,因为结果数组中的元素可能出现重复 因此应该先排序,然后左右夹逼 用0减去[0,nums.size()-2)中的一个数得到一个sum 在剩余子数组中找到两数之和等于sum即可 将问题转...

2018-06-26 20:51:56

LeetCode-001. Two Sum

1. 题目Two Sum 查找数组中和为特定值的两个数,返回其下标 假定每个输入都有一个解决方案,你不会使用同一元素两次2. 分析本题需要返回的是下标,而不是数字本身 所以不同于 S中是否存在两个其和刚好为x的元素 可以借助哈希表,保存数组中每个数的下标 遍历数组的同时在哈希表中查找即可3. 代码1)class Solution {publi...

2018-06-24 15:24:41

S中是否存在两个其和刚好为x的元素

《算法导论》第3版习题2.3-7:描述一个运行时间为O(nlgn)的算法,给定n个整数的集合S和一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素。首先对S[0…n-1]进行非降序排序,然后左右夹逼即可 时间复杂度分析:排序为O(nlgn),左右夹逼为O(n),最终O(nlgn)bool find(int A[], int len, int target){ if (l...

2018-06-24 14:53:51

LeetCode-081. Search in Rotated Sorted Array II

1. 题目Search in Rotated Sorted Array II 在旋转有序数组中查找特定值 数组中有重复的数,查找特定值,若存在,返回true,若不存在,返回false 如[10,12,12,1,2,6,8,10] 10 返回true [10,12,12,1,2,6,8,10] 0 返回false2. 分析类似于 Search in Ro...

2018-06-23 16:07:16

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!