点击蓝色“五分钟学算法”关注我哟
加个“星标”，天天中午 12:15，一起学算法
作者 | 程序员小吴
来源 | 五分钟学算法
今天分享一道简单的笔试题，题目来源于京东校园招聘笔试真题。你做出这道简单的题目需要花费多少东分钟呢？
题目描述 
有一个有序表为 {1，5，8，11，19，22，31，35，40，45，48，49，50} ，当二分查找值为 48 的结点时，查找成功需要比较的次数（ ）
A、4
B、3
C、2
D、1
题目分析 
一道送分题。
有序表的长度为 13，根据 二分查找法 查找数的特性，每次都  n/2 进行折半查找。
13 / 2 = 6
6 / 2 = 3
3 / 2 = 1
1 / 2 = 0
最多需要 4 次就能得出结果。
这道题目需要查找的是 48 ，列表下标索引从零开始标记。
第一次，求出 [0，12] 中间节点。
0 + （12 - 0） / 2 = 6 

a[6] = 31 < 48
区间变为 [7，12]。
第二次，求出 [7，12] 中间节点。
7 + （12 - 7） / 2 = 9 

a[9] = 45 < 48
区间变为 [10，12]。
第三次，求出 [10，12] 中间节点。
10 + （12 - 10） / 2 = 11 

a[11] = 49 > 48
区间变为 [10，11]。
第四次，求出 [10，11] 中间节点。
10 + （11 - 10） / 2 = 10

a[10] = 48 = 48
找到啦！
---
以上，便是今日分享，觉得不错，还请点个在看，谢谢～
推荐阅读：



啦，欢迎点击阅读原文进行访问~

                
  

                    

                    

                    
                    
                    
点击关注上方“五分钟学算法”，
设为“置顶或星标”，第一时间送达干货。
转自面向大象编程，作者nettee
题目描述
这是一道经典的面试题了，也叫做 “Top K 问题”。解决这个问题有两种常用的方法：堆方法、分治法。分治法的思想和快速排序相同。
本篇题解分别讲解了两种方法，并比较了它们的适用场景。
题目解析
这道题是一个经典的 Top K 问题，是面试中的常客。Top K 问题有两种不同的解法，一种解法使用堆（优先队列），另一种解法使用类似快速排序的分治法。这两种方法各有优劣，最好都掌握。本文用图解的形式讲解这道问题的两种解法，包括三个部分：
方法一：堆，时间复杂度
方法二：快排变形，（平均）时间复杂度
两种方法的优劣比较
方法一：堆 
比较直观的想法是使用堆数据结构来辅助得到最小的 k 个数。堆的性质是每次可以找出最大或最小的元素。我们可以使用一个大小为 k 的最大堆（大顶堆），将数组中的元素依次入堆，当堆的大小超过 k 时，便将多出的元素从堆顶弹出。我们以数组 ，  为例展示元素入堆的过程，如下面动图所示：
这样，由于每次从堆顶弹出的数都是堆中最大的，最小的 k 个元素一定会留在堆里。这样，把数组中的元素全部入堆之后，堆中剩下的 k 个元素就是最大的 k 个数了。
注意在动画中，我们并没有画出堆的内部结构，因为这部分内容并不重要。我们只需要知道堆每次会弹出最大的元素即可。在写代码的时候，我们使用的也是库函数中的优先队列数据结构，如 Java 中的 PriorityQueue。在面试中，我们不需要实现堆的内部结构，把数据结构使用好，会分析其复杂度即可。
以下是题解代码。感谢评论区提醒，这里的代码可以做一些优化，如果当前数字不小于堆顶元素，数字可以直接丢掉，不入堆。下方的代码已更新：
public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0) {
        return new int[0];
    }
    // 使用一个最大堆（大顶堆）
    // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
    Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

    for (int e : arr) {
        // 当前数字小于堆顶元素才会入堆
        if (heap.isEmpty() || heap.size() < k || e < heap.peek()) {
            heap.offer(e);
        }
        if (heap.size() > k) {
            heap.poll(); // 删除堆顶最大元素
        }
    }

    // 将堆中的元素存入数组
    int[] res = new int[heap.size()];
    int j = 0;
    for (int e : heap) {
        res[j++] = e;
    }
    return res;
}
算法的复杂度分析：
由于使用了一个大小为 k 的堆，空间复杂度为 ；
入堆和出堆操作的时间复杂度均为 ，每个元素都需要进行一次入堆操作，故算法的时间复杂度为 。
方法二：快排变形 
Top K 问题的另一个解法就比较难想到，需要在平时有算法的积累。实际上，“查找第 k 大的元素”是一类算法问题，称为选择问题。找第 k 大的数，或者找前 k 大的数，有一个经典的 quick select（快速选择）算法。这个名字和 quick sort（快速排序）看起来很像，算法的思想也和快速排序类似，都是分治法的思想。
让我们回顾快速排序的思路。快速排序中有一步很重要的操作是 partition（划分），从数组中随机选取一个枢纽元素 v，然后原地移动数组中的元素，使得比 v 小的元素在 v 的左边，比 v 大的元素在 v 的右边，如下图所示：
这个 partition 操作是原地进行的，需要  的时间，接下来，快速排序会递归地排序左右两侧的数组。而快速选择（quick select）算法的不同之处在于，接下来只需要递归地选择一侧的数组。快速选择算法想当于一个“不完全”的快速排序，因为我们只需要知道最小的 k 个数是哪些，并不需要知道它们的顺序。
我们的目的是寻找最小的  个数。假设经过一次 partition 操作，枢纽元素位于下标 ，也就是说，左侧的数组有  个元素，是原数组中最小的  个数。那么：
若 ，我们就找到了最小的  个数，就是左侧的数组；
若  ，则最小的  个数一定都在左侧数组中，我们只需要对左侧数组递归地 partition 即可；
若 ，则左侧数组中的  个数都属于最小的  个数，我们还需要在右侧数组中寻找最小的  个数，对右侧数组递归地 partition 即可。
这种方法需要多加领会思想，如果你对快速排序掌握得很好，那么稍加推导应该不难掌握 quick select 的要领。
以下是题解代码：
public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0) {
        return new int[0];
    } else if (arr.length <= k) {
        return arr;
    }
    
    // 原地不断划分数组
    partitionArray(arr, 0, arr.length - 1, k);
    
    // 数组的前 k 个数此时就是最小的 k 个数，将其存入结果
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = arr[i];
    }
    return res;
}

void partitionArray(int[] arr, int lo, int hi, int k) {
    // 做一次 partition 操作
    int m = partition(arr, lo, hi);
    // 此时数组前 m 个数，就是最小的 m 个数
    if (k == m) {
        // 正好找到最小的 k(m) 个数
        return;
    } else if (k < m) {
        // 最小的 k 个数一定在前 m 个数中，递归划分
        partitionArray(arr, lo, m-1, k);
    } else {
        // 在右侧数组中寻找最小的 k-m 个数
        partitionArray(arr, m+1, hi, k);
    }
}

// partition 函数和快速排序中相同，具体可参考快速排序相关的资料
// 代码参考 Sedgewick 的《算法4》
int partition(int[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    int v = a[lo];
    while (true) {
        while (a[++i] < v) {
            if (i == hi) {
                break;
            }
        }
        while (a[--j] > v) {
            if (j == lo) {
                break;
            }
        }

        if (i >= j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, lo, j);

    // a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
上述代码中需要注意一个细节（评论区有好几个小伙伴问到，这里补充说明一下）：
partitionArray 函数中，两次递归调用传入的参数为什么都是 k？特别是第二个调用，我们在右侧数组中寻找最小的 k-m 个数，但是对于整个数组而言，这是最小的 k 个数。所以说，函数调用传入的参数应该为 k。
该代码的成绩还是非常好的：
算法的复杂度分析：
空间复杂度 ，不需要额外空间。
时间复杂度的分析方法和快速排序类似。由于快速选择只需要递归一边的数组，时间复杂度小于快速排序，期望时间复杂度为 ，最坏情况下的时间复杂度为 。
两种方法的优劣性比较 
在面试中，另一个常常问的问题就是这两种方法有何优劣。看起来分治法的快速选择算法的时间、空间复杂度都优于使用堆的方法，但是要注意到快速选择算法的几点局限性：
第一，算法需要修改原数组，如果原数组不能修改的话，还需要拷贝一份数组，空间复杂度就上去了。
第二，算法需要保存所有的数据。如果把数据看成输入流的话，使用堆的方法是来一个处理一个，不需要保存数据，只需要保存 k 个元素的最大堆。而快速选择的方法需要先保存下来所有的数据，再运行算法。当数据量非常大的时候，甚至内存都放不下的时候，就麻烦了。
所以当数据量大的时候还是用基于堆的方法比较好。
END
● 二叉树问题太复杂？「三步走」方法解决它！
● 五分钟学算法：什么是堆？
● 一个我超喜欢的动态博客系统，五分钟即可部署上线！
● 五分钟学算法：什么是线段树？
点“在看”你懂得 

				

给大家推荐一个Github排名前50的大佬公众号:五分钟学算法
这个大佬在 Github 上有 50000star，专注于图解算法，已经帮助了数万名初学者入门学习算法。
关注他的公众号在后台回复 1024 送你 50 本算法编程书籍。

如果你要看各个技术栈的学习路线，可以在这个「学习路线」的专题看：https://www.iamshuaidi.com/?p=277，   这个专题的粒度比「学习路线」更细，会具体讲解各个科目的学习以及核心掌握的知识点。

如何学习算法的相关文章，大家估计也见过不少，每个人的学习方法都不尽相同，这很正常，并且，对于不同的选手，例如打 ACM 的玩家和不打比赛的玩家来说，训练的方式也会有所差异，所以别人所说的学习方式，更多的是作为你的一种参考。
在我的四年大学里，花在学习数据结构/算法的时间可以说是最多的了，不过我并不后悔，因为算法基础的沉淀，给我后面的成长带来了很多帮助，所以今天这篇文章，帅地会根据自己的理解，谈一谈如何学习算法，如果你是这方面的小白的话，还是可以参考一下。
不过，在写之前，我想先回答几个问题，或许对于那些刚入门的同学，有些许帮助。
一、简单回答几个问题
1、有必要学算法吗？
很多过来人可能都会跟你说，算法没必要学，你又不是算法岗，工作其实就天天 crud，用啥都是封装好的，学了也用不到，慢慢也就忘了。
这篇文章不是来跟你辩论有没有必要学算法的，我就做个简单的回答，我的答案是，有必要学一学，一个现实且势利的原因，估计就是 ----- 大厂都喜欢考察算法了，不信你去问问刚刚参加过 2020 校招的同学，我自己也参加过 2019 的秋招，算法考察，基本无处不在，如果想要获得面试机会，那么就得笔试，而笔试，大部分公司都是编程题，即算法题，而且，面试中也会经常问到算法，数据结构。显然，从找公司的角度看，不学算法你会失去很多面试的机会。然而，更重要的还是，程序 = 数据结构 + 算法，算法基本功打好，可以让我们走的更远。
2、学算法好慢/好难，是我不够聪明不适合学算法吗？
答不是的，如果只是学习下常见算法，以后应付下面试/笔试 + 分析下工作遇到的一些问题，那么我觉得，还论不到天赋来做审判，这绝对不是鸡汤，当然，如果你想打 ACM，拿各种奖的，那我就不大清楚了。
简单的说，学算法好慢/好难主要还是你代码写的太少了，做的题太少了，虽然有些人学起来会慢一些，特别是入门那会，但一旦过了这道坎，学起来就会快很多，所以，不要还没学之前，或者学了一时半会觉得自己没有 get 到点，就否定自己。
二、入门数据结构与算法
我是学习了《数据结构与算法分析》这本书之后，再去学习各种算法思想 + 刷题的，所以我觉得，入门算法的第一步，是在你学会了一门语言之后（帅地当时学的是 C 语言），静下心来啃一本数据结构与算法的书籍，例如我说的《数据结构与算法分析:xx语言描述版》，也可以是《大话数据结构》等等。
怎么学这本书呢？
我觉得，对于刚刚入门的选手来说，没啥技巧，也不要迷恋于各种快捷的方法，咱们老实点，当个普通人，就跟着书学，按照顺序学就可以了，然后把里面例子的代码，都至少打一遍，当然，还需要跑通，结果要符合预期，如果不符合，就调试到符合预期。
注意，上面那句话我打了颜色，说明这句话非常重要，千万不要觉得自己理解了，就不写代码了，例如觉得自己理解了链表的增删改，然后就不写代码了，在编程这一块，感觉自己理解，和成功实现且符合预期，特么就是两回事。
之后每一章都会有习题，不需要全部做，自己挑几道做就好了，就算是一眼就秒杀知道怎么做的，其实也可以实现一遍，如果不懂，可以找答案，但是一定要自己在电脑上把代码敲打出来，然后跑通。当你把书上 90% 的代码例子跑通，那么，这本书有一半的知识，就是你的了。
这里我说下，你们找的书籍，最好是有完整代码实现的，因为有些书籍，为了具有通用性或者严谨性，是采用伪代码来实现的，我不建议初学者用这类书籍，因为容易一脸蒙蔽，代码也不好跑通验证，所以如果你觉得自己是普通人，那么就找一本有完整代码的书籍来看吧，然后乖乖把代码的代码敲打跑通起来。
不要眼高手低，当你积累到一定的代码数量，你就会慢慢来感觉了。
当你学完了链表、队列、栈、二叉树、哈希表等最基本的数据结构，其实你就算入门了，这个时候其实你已经具备了去 leetcode 刷题的能力了。不过在学习过程中，特别是到了图那部分，会涉及到很多算法，例如最短路径，深度搜索和广度搜索…当然，还有二叉树的各种遍历等。
如果你对递归一点也不懂，那么你会被虐的，脑袋也容易被爆栈，因为，递归真的无处不在，这也引出了我觉得入门算法非常重要的一个算法思想 — 递归算法。
三、刷题之前的一些准备
如果你连最基本的数据结构，例如链表，队列，栈，二叉树都没有接触过，那么我是不建议你去 leetcode 刷题的，所以我上面先说了先入门一下数据结构与算法，当你学习了这些基础的数据结构之后，其实已经具备了刷题的能力了。
不过，我还是希望你能在学习一些算法思想，一般就这几种
1、递归
2、枚举
3、贪心
4、回溯
5、动态规划
但是，其中最重要的，我觉得就是递归，其他的几种算法，也都会有递归的影子，并且我刚才说图相关算法、二叉树的遍历等，也都包含递归的使用。
所以，在你刷题之前，或者在学习二叉树、图相关算法遇到递归的时候，我希望你能静下心来，去学一学递归，我也会告诉你，对于初学者，递归很难，我是被无数次折腾，无数次看答案似懂非懂之后，才突然醒悟了。
你不需要把它学的很精通，但是你要懂一些基本的递归题，知道递归是怎么一回事，例如最简单的斐波那契数列得会用递归做吧？阶乘也会吧（虽然不是最优解）。
所以，死磕入门数据结构，可以学习下一些算法思想，而递归，你必须得入门，至于动态规划、回溯，我觉得慢点学也没有，可以后面刷题遇到时在学，而枚举、贪心，相对比较简单。
关于递归的，可以看我之前的一遍入门级的文章：为什么你学不会递归？告别递归，谈谈我的一些经验
评价还是很好，之后找些简单的题做，例如在 LintCode 那些 easy 的题（leetcode 和 lintcode 类似，类似于一个中文版，一个英文版）
这里给大家推荐一份 Github 上的开源刷题笔记，好几种算法思想都讲解了，下载链接：BAT大佬的刷题笔记太经典
给大家看一下目录


四、如何刷题
终于，到了刷题这一部分了，如果要说学算法的捷径，那么刷题便是最好的捷径，如果你刷的题很少，达不到一定的量，那么再多的捷径，估计也没啥用，只有在满足一定题量的情况下，才适合来谈论所谓的技巧。
1、先说一说笔试
不过在刷题之前我想先说一说笔试，如果笔试不考算法，面试也不考算法，那么我可能在学习算法的这条路上，会少了很多的积极性，你可能会觉得我很功利，但是我觉得，带着功利性的目的去学习算法，也是完全没问题的。
在校招的笔试中，其实这些笔试题还是挺难的，你在 leectode 可以做出 hard 级别的题，但在笔试中，可能连 medium 级别的都做不出，因为笔试的题，都比较灵活，基本都会通过实际的例子来引出一道题，你可能不知道要使用哪种方法来做比较好，有些还是多种方法的结合。
对于笔试的题型，我之前也总结过，无非是以下几种
（1）、基本数据结构的考察：这类题我觉得是比较简单的，主要考场基本数据结构的操作，例如二叉树的层序遍历，链表的逆序等，当然，它不会直接告诉你，让你来逆序或者遍历。
（2）、某种算法思想的掌握：这类题你掌握了某种算法思想，就会比较容易，如果不懂，那就凉凉了。例如动态规划、回溯、枚举、深度/广度、贪心、二分等。其中，我觉得动态规划考的挺多，还要就是 回溯+深度/广度。
（3）、边界条件的考察：这类型的题，估计你一看就有思路，知道该怎么做，但是，它的边界条件特别多，需要分很多种情况来讨论，特别容易出错，有时候会让人陷进去，越做越复杂，这类题主要考场你的思维严谨程度。
（4）、找规律、数学公式：这类型的题，主要是根据数据之间的一些关系，来找一些规律，进而推出他们的通用公式，就像我们高中时，找数列的同项一样。
2、按分类刷题
上面我列了笔试的题型，并且跟你说了笔试是真的挺难的，那么对于我个算法小白来说，该如何做好呢？
我的建议是，分类刷题，阶段性总结。例如最开始可以在 LintCode 按照链表/二叉树/递归等这些标签来刷，因为这样可以让你深入掌握每一种方法。
当然，笔试的题之所以难，是因为我们往往不知道用哪一种方法做好，或者说具体属于哪一种题型，那么还有必要分类刷题吗？
答是有必要的，只有当你熟悉每一种题型，你才能灵活使用他们，进而解决各类复杂的题，这就如同你在练功夫的时候，前期你需要把每个招式都打扎实了，之后才能灵活把各个招式连接起来，融合贯通。刷题也是一样，前期先分类，把每个题型掌握起来，后期咱们再随机练习，慢慢着就能灵活应用了。
不过，每次刷了一部分题型之后，我觉得还有必要做一些总结，或者说总结一些刷题模版，例如对于二分法查找，其实好几种题型总结起来，就是开闭区间的组合，你可以把他们总结起来，例如什么时候用开区间，什么时候用闭区间。
有人可能会说，模版是死的，真的有必要总结吗？
我觉得有必要总结，但没必要死记，总结，只是加深你的理解，当然，如果你在做题的时候，刚好记住了自己的模版，可以直接套上去，那肯定更好。但是，就算忘了也没事，通过自己的总结，你其实是知道怎么做的了，只是还需要你多花一点时间，快速模拟讨论下各种情况，一样能够做出来的。
也就是说，最开始刷题的时候，可以分类刷题，并且阶段性总结，如果你是初学者，可以先从简单的题做起，例如我刚才说的，简单的递归题，之后一些二叉树、链表的题，因为你可能刚刚学习数据结构不久，刚好可以加深你的理解。
五、刷题时的一些注意点
当我们在做一道题的时候，可能会遇到两种情况，一种是这道题，特么秒杀，一眼就懂思路；一种是，一脸蒙蔽，太难了吧。
一眼就懂思路，有必要做吗？
我的答案是，有必要做。千万不要眼高手低，看着简单，做起来不一定简单，AC 之后，你还要去讨论区看看大佬们是怎么做的，因为有些人的代码，真的写的很简洁，看着就很舒服，咱们可以多学一学的，当然，也有可能那个人就是你自己。
代码写多了，有时候，你就会发现自己真的变强了，写起代码来，bug 也越来越少了，分分钟 AC 一道题。
尽量最优解
其实对于很多题，如果不看时间复杂度和空间复杂度，单单只是 AC，那还是很容易的，但是一提交，你的代码可能只打败了百分之几的人，显然我们是不能满足于这种代码的。
当你做一道题时，一开始可以先暴力做，但后面，还得想想该如何优化，想不出也没事，可以讨论区找空间/时间复杂度更低的代码，或者直接搜索引擎搜索，一般都能搜到别人的代码。
之后跟着别人的代码，自己再实现一波，尽可能把最优解的代码实现起来。千万不要为了 AC 而 AC，不是 AC 的越多就越强的，当你入门之后，更多的是要总结方法，寻找高效率的代码。
这里推荐一份 leetcode 开源刷题笔记，汇聚了上千道 leetcode 题解，并且代码都是 beat 100%：
下载链接：leetcode 分类题解（最优解）
六、总结
说到算法的学习方式，对我来说，真的没有什么捷径之类的，就是像我上面说的，先找本书死磕入门数据结构，就跟着书的例子，把例子跑起来就好了，跑起来也不是一件简单的事情。之后就去接触下一些算法思想，后面就可以分类刷题了，刷题就是最好的捷径了。
当然，不要 AC 之后就完事了，应该尽可能寻找最优解，当你积累了一定的题量，那么你真的会发现自己变强了，突然感觉递归也就那么一回事。
我学习算法时，基本看书 + 网上刷题，也很少看视频，因为我觉得看视频比较花时间，不过我之前在班里还是看到部分人喜欢看视频的，至于看书好还是看视频好，这个看个人喜好吧，也没有说哪种就一定更好。
这里给大家推荐两本大佬总结的刷题笔记：

下载链接：BAT大佬的刷题笔记太经典
把这份笔记突击学习一下，很多算法考察，基本都稳了
另外，再给大家推荐一份某大佬的 leetcode 刷题笔记，汇聚了上千道 leetcode 题解，并且代码都是 beat 100%：
下载链接：leetcode 分类题解（最优解）
最后，帅地还是希望大家能够静下心来，好好学习下数据结构与算法，我觉得最沉得下心的阶段就是大一大二了，所以这个时间点，是学习算法的最佳时间，千万不要想着我先学别的，以后再来学，以后学可能会理解的更加深刻。
不要想太多了，你以后怕是更加懒的学，你以后会很难静下心来学的。所以，千万不要想以后，现在，就是最佳的学习时间。
作者简洁

作者：大家好，我是帅地，从大学、自学一路走来，深知算法，计算机基础知识的重要性，公众号「帅地玩编程」10万粉丝作者，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我一起学习，点击了解我四年大学学习之路 转载说明：未获得授权，禁止转载