2020年Java程序员面试算法宝典附答案

    2020年Java程序员面试算法宝典附答案，众所周知，算法可以说是大厂面试Java程序员的必问面试题。相信算法的重要性大家都了解，好的算法可以让性能得到万倍提升，做到毫秒级处理千万数据的程度。因此，为了提升大家在面试中的底气，跟着小编往下看：

    1、算法的时间复杂度时候是什么？

    答案：算法的时间复杂度表示程序运行完成所需的总时间，它通常用大O表示法来表示。

    2、合并k个有序（假设升序）数组的具体步骤是什么？

    答案：将k个数组的第一个元素取出来，维护一个小顶堆；弹出堆顶元素存入结果数组中，并把该元素所在数组的下一个元素取出来压入队中；调整堆的结构，使其满足小顶堆的定义；重复前两步直到合并完成。

    3、解释二分法检索如何工作？

    答案：在二分法检索中，我们先确定数组的中间位置，然后将要查找的值与数组中间位置的值进行比较，若小于数组中间值，则要查找的值应位于该中间值之前，依此类推，不断缩小查找范围，直至得到最终结果。

    代码拓展，二分法查找

    defBinarySearch(t,x):

    t.sort()#对列表进行排序，列表是有序的，是二分法的前提

    low=0;

    high=len(t)-1;

    whilelow<high:

    mid=(low+high)/2;

    ift[mid]<x:

    low=mid+1;

    elift[mid]>x:

    high=mid-1;

    else:

    returnmid

    returnNon

    4、查找数组中出现次数超过一半的数字

    答案：等价于求数组中第n/2大的数，和4中思想一样，平均时间复杂度O(n)

    5、一个数组怎么输出前K大的值、时间复杂度？

    答案：借助快排partition的思想，平均时间复杂度是O(n)

    6、用A表示1第一列，B表示2第二列，。。。，Z表示26，AA表示27，AB表示28。。。以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。

    答案：这道题的解题思路关键在于26进制转10进制。

    7、输入一个正数n，输出所有和为n连续正数序列。

    答案：输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

    8、输出一个整数二进制表示中1的个数。

    答案：这道题的解法多样，可以右移原数判断，如果输入是负数可能陷入死循环；也可以左移1；还可以把一个整数-1后与原数做与运算会消去原数最左边的1。

    9、在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

    答案：这道算法面试题对大多数Java程序员来讲并不难，大致的解题思路如下，我们注意到这个二维数组的行和列都是升序的，也就是说最上面的一行和最右边的一列在整体上也是升序的，在一个排序数组上查找某个我们会很自然的想起二分法。这样我们每次都把要查找的数和当前剩下的二维数组的右上角数字比较，这样每次我们都可以排除掉一行或一列。算法的时间复杂度是O(n+m)，也就是行数加列数。

    10、两个排序数组A1和A2，现在想把A2插入A1中并仍保持有序。

    答案：数组是个顺序表，我们往数组中插入某个数的话必须要移动当前位置后面所有的数。常规的思路是每次插入一个数并移动后面的数，这样多次插入后会导致数组中有的数被移动了多次，极大浪费了效率。我们希望每个数移动一次就到达它最终的位置，所以我们往往会反向移动数组，这样做的好处是移动当前数时后面的数已经到达了最终位置，我们移动当前数不会影响到后面的数，这样就确保了每个数只被移动一次。

　以上就是动力节点java培训机构的小编针对“2020年Java程序员面试算法宝典附答案”的内容进行的回答，希望对大家有所帮助，如有疑问，请在线咨询，有专业老师随时为你服务。