java-在给定的数组段中查找最小数目
发布时间：2020-12-14 19:26:34 所属栏目：Java 来源：网络整理
导读：假设我们有大量的整数A.我们想回答许多查询,例如： 在索引0到100之间找到最小值 在索引4和90之间找到最小值 示例：A = {6,1,7,5,3} 索引0和1之间的最小值为1 索引2和3之间的最小值是5 索引0和4之间的最小值为1 对于性能而言,遍历每个查询的元素并查找最小值
|
假设我们有大量的整数A.我们想回答许多查询,例如： >在索引0到100之间找到最小值 示例：A = {6,1,7,5,3} >索引0和1之间的最小值为1 对于性能而言,遍历每个查询的元素并查找最小值的明显方法还不够.我需要以某种方式存储所需的信息,然后在固定时间内回答查询.因此,算法不应为二次方.需要比O(N * M)更好的东西. (N：数组大小,M：查询数) 我尝试过,但找不到解决方法.它一定是关于寻找和存储一些和以某种方式使用它们的东西.有任何想法吗？谢谢阅读. 最佳答案
要考虑的两个选项：
> O(n)预计算和每个查询的O(logn) 第一个通过递归计算偶数位置上所有对的最小值,然后在4的倍数上的所有4处递归计算最小值,然后在8的所有倍数上的所有8进行递归计算.然后,每当您要访问特定范围的最小值时,便将其分解为已有的部分并计算其中的最小值. 例如,要查找元素1..10的最小值,请使用元素1和2..3以及4..7和8..9和10的最小值. 第二种方法是计算所有位置上所有对的最小值,然后计算所有位置上的所有4,然后计算所有位置上的所有8.当您具有特定范围时,可以将其构造为两个部分中的最小值,然后计算这两个部分中的最小值. 例如,请使用元素1..8的最小值和元素3..10的最小值. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |