发布于2021-07-18 20:03 阅读(1021) 评论(0) 点赞(17) 收藏(1)
大家好,我是陈哈哈,北漂五年。相信大家和我一样,
都有一个大厂梦
,作为一名资深Java选手,深知面试重要性,接下来我准备用100天时间,基于Java岗面试中的高频面试题,以每日3题
的形式,带你过一遍热门面试题及恰如其分的解答。
一路走来,随着问题加深,发现不会的也愈来愈多。但底气着实足了不少,相信不少朋友和我一样,日积月累才是最有效的学习方式!想起高三时一个同学的座右铭:只有沉下去,才能浮上来。
共勉(juan)。
群里朋友们都表示好熟悉的画面!是的,我也感到亲切,这是哪?生活。
作者:Zifeng-Fan
本栏目Java开发岗高频面试题主要出自以下各技术栈:Java基础知识
、集合容器
、并发编程
、JVM
、Spring全家桶
、MyBatis等ORMapping框架
、MySQL数据库
、Redis缓存
、RabbitMQ消息队列
、Linux操作技巧
等。
快速排序,顾名思义就是一种以效率快为特色的排序算法,快速排序(Quicksort
)是对冒泡排序的一种改进
。由英国计算机专家:托尼·霍尔(Tony Hoare)在1960年提出。
从排序数组中找出一个数,可以随机取,也可以取固定位置,一般是取第一个或最后一个,称为基准数。然后将比基准小的排在左边,比基准大的放到右边;
如何放置呢,就是和基准数进行交换,交换完左边都是比基准小的,右边都是比较基准大的,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解(子数组只有一个值)为止。以此达到整个数据变成有序序列。
快速排序采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod),现在各种语言中自带的排序库很多使用的都是快速排序。
空间复杂度
快速排序是一种原地排序,只需要一个很小的栈作为辅助空间,空间复杂度为O(log2n),所以适合在数据集比较大的时候使用。
时间复杂度
时间复杂度比较复杂,最好的情况是O(n),最差的情况是O(n2),所以平时说的O(nlogn),为其平均时间复杂度。
算法步骤
分别对左右子序列继续递归重复前三步操作
,直到左右子序列长度只有单个元素为止。demo示例
实例数组:arr[] = {19,97,9,17,1,8};
快速排序中的规则:右边有坑,就从左边Arr[L + n]取值来填,反之左边有坑,则从右边Arr[R - n]取值来填;
匹配规则:大于基准值的插入到Arr[R],如果小于,则直接忽略并跳过,继续向右取值,直到坐标L和坐标R重合。
package com.softsec.demo;
/**
* Created with IDEA
*
* @Author Chensj
* @Date 2020/5/17 19:04
* @Description
* @Version 1.0
*/
public class quickSortDemo {
public static void main(String[] args) {
// 创建测试数组
int[] arr = new int[]{19,97,9,17,1,8};
System.out.println("排序前:");
showArray(arr); // 打印数组
// 调用快排接口
quickSort(arr);
System.out.println("\n" + "排序后:");
showArray(arr);// 打印数组
}
/**
* 快速排序
* @param array
*/
public static void quickSort(int[] array) {
int len;
if(array == null
|| (len = array.length) == 0
|| len == 1) {
return ;
}
sort(array, 0, len - 1);
}
/**
* 快排核心算法,递归实现
* @param array
* @param left
* @param right
*/
public static void sort(int[] array, int left, int right) {
if(left > right) {
return;
}
// base中存放基准数
int base = array[left];
int i = left, j = right;
while(i != j) {
// 顺序很重要,先从右边开始往左找,直到找到比base值小的数
while(array[j] >= base && i < j) {
j--;
}
// 再从左往右边找,直到找到比base值大的数
while(array[i] <= base && i < j) {
i++;
}
// 上面的循环结束表示找到了位置或者(i>=j)了,交换两个数在数组中的位置
if(i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// 将基准数放到中间的位置(基准数归位)
array[left] = array[i];
array[i] = base;
// 递归,继续向基准的左右两边执行和上面同样的操作
// i的索引处为上面已确定好的基准值的位置,无需再处理
sort(array, left, i - 1);
sort(array, i + 1, right);
}
/**
* 数组打印
* @param num
*/
private static void showArray(int[] num) {
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}
坐标:深圳
作者:對你何止一句钟意
我:???
函数内部调用的自身函数的编程技巧称为递归(recursion)。
构成递归的条件
:
优点
:
简洁
在树的前序,中序,后序遍历算法中,递归的实现明显要比循环简单得多。
缺点
:
递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。(效率)
递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算,如fibonacci斐波那契数列的递归实现。(效率)
调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出。(性能)
例如递归计算一下n的阶乘
package com.softsec;
/**
* 递归计算n的阶乘
* @author Chenhh
*/
public class demo {
public static void main(String[] args) {
System.out.println(recursion(5));
}
/**
* 递归计算n的阶乘
*/
private static int recursion(int n) {
if (n <1) {
throw new IllegalArgumentException("参数必须大于0");
} else if (n == 1) {
return 1;
} else {
return n * recursion(n - 1);
}
}
}
课间休息,又来秀一下来自咱们群里同学的搬砖工地,坐标:大连。
作者:Onlooker
先拿100000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(100000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的100000个数就是所需的最大的100000个。建堆时间复杂度是O(m),算法的时间复杂度为1次建堆时间+n次堆调整时间=O(m+nlogm)=O(nlogm)(n为10亿,m为100000)。
优化的方法
:可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的100000个数
,合并到一起在再找出最终的结果。
top K问题
在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。
针对top K类问题,通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆)
,即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树活着Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。
对于有10亿个整数,如何找出其中最大的10万个这个问题
最容易想到的方法是将数据全部排序
,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是如果按每个int类型占4个字节,10亿个整数就要占用4G的存储空间
,对于一些java运行内存小于4G的计算机而言,直接OOM
(out of memory)了。其实即使内存能够满足要求(我机器内存都是8GB),该方法也并不高效,因为题目的目的是寻找出最大的100000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。
第二种方法为局部淘汰法
,该方法与排序方法类似,用一个容器保存前100000个数,然后将剩余的所有数字——与容器内的最小数字相比
,如果所有后续的元素都比容器内的100000个数还小,那么容器内这个100000个数就是最大100000个数。如果某一后续元素比容器内最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即100000。
第三种方法是分治法
,将10亿个数据分成1000份,每份100万个数据,找到每份数据中最大的100000个,最后在剩下的1000 * 100000个数据里面找出最大的100000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的100000个数据的方法如下:用快速排序的方法,将数据分为2堆
,如果大的那堆个数N大于100000个,继续对大堆快速排序一次分成2堆
,如果大的那堆个数N大于100000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于100000个,就在小的那堆里面快速排序一次,找第100000-n大的数字;递归以上过程,就可以找到第10w大的数。参考上面的找出第10w大的数字,就可以类似的方法找到前100000大数字了。此种方法需要每次的内存空间为10^6*4=4MB,一共需要101次这样的比较。
第四种方法是Hash法
。如果这1亿个书里面有很多重复的数,先通过Hash法,把这10亿个数字去重复
,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的100000个数
。
第五种方法采用最小堆
。首先读入前100000个数来创建大小为100000的最小堆,建堆的时间复杂度为O(m)(m为数组的大小即为100000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆
。整个过程直至10亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有100000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是100000(常数)。
今天我们复习了面试中常考的三个算法问题,你做到心中有数了么?对了,如果你的朋友也在准备面试,请将这个系列扔给他,如果他认真对待,肯定会感谢你的!!
好了,今天就到这里,学废了的同学,记得在评论区留言:打卡。
,给同学们以激励。
原文链接:https://blog.csdn.net/qq_39390545/article/details/118686043
作者:火腿快跑
链接:http://www.pythonpdf.com/blog/article/72/9adc0dbd7c4b17909658/
来源:编程知识网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!