Java 程序用于查找数组中给定索引范围的 GCD
在数据结构领域,范围查询是一种预处理方法,用于高效地对某些输入数据进行操作。范围查询负责回答任何数据子集上特定输入的任何查询。如果我们想从表中复制一些数据列,我们需要为该特定数据集维护一个索引。索引是直接链接或键,旨在提供数据集中的高效搜索过程。它主要用于加快从丢失的数据源中检索数据的速度。
在数学中,最大公约数又名 GCD 是一个最大的整数,它可以整除作为输入的两个整数。这里,所有数字都必须具有非零值。举个例子 -
70, 80 的 GCD = 10(10 是能整除它们的最大数,余数为 0) 42, 120, 285 的 GCD = 3(3 是能整除它们的最大数,余数为 0)
算法找出数组中给定索引范围的 GCD(详述)
步骤 1 - 开始
步骤 2 - 构造 arr[0] 到 arr[n-1] 的部分
步骤 3 - 继续相等划分
步骤 4 - 递归调用这两个部分
步骤 5 - 对于每个部分,仅保存最大公约数值将保存在线段树中
步骤 6 − 构建另一个线段树,从底部到顶部填充它
步骤 7 − 每个节点存储具有一定范围的 GCD 的一些数据
步骤 8 − 如果节点范围是 startQuery 和 endQuery,则返回一个值节点
步骤 9 − 否则,如果范围无效,它将返回 null 或 -1 作为输出
步骤 10 − 否则,返回 GCD 函数作为递归调用
步骤 11 − 终止
在数组中查找给定索引范围的 GCD 的算法(简而言之)
步骤 1 − 假设 a 和 b 是两个非零整数
步骤 2 - 设 a mod b = R
步骤 3 - 如果 a=b 且 b=R
步骤 4 - 然后,重复步骤 2 和步骤 3
步骤 5 - 进程将运行,直到 a mod b 大于零
步骤 6 - GCD = b
步骤 7 - 终止
用于在数组中查找给定索引范围的 GCD 的语法
Begin
if c = 0 OR d = 0, then
return 0
if c = d, then
return b
if c > d, then
return findGCD(c-d, d)
else
return findGCD(c, d-c)
End
在此语法中我们可以看到可能的逻辑代码,如何找到两个非零数字的最大公约数。该过程的时间复杂度为 O(Q*N*log(Ai)),辅助空间的评估为 O(1)。
方法
方法 - 使用线段树在给定范围内查找数字的 GCD 的程序
使用线段树在给定范围内查找数字的 GCD 的程序
要使用线段树在给定范围内查找数字的 GCD,我们需要遵循一些不可避免的步骤。
线段树的构造
输入数组的元素是叶节点。
每个单独的内部节点代表所有叶节点的 GCD。
数组表示可以通过线段来完成树。
-2*(i+1),索引的左元素
-2*(i+2),索引的右元素
-Parent 为 floor((i-1)/2)
使用给定数组构造新的线段树:
以线段 arr[0 . . . ] 开始该过程。 n-1]。
将它们分成两半。
对两半调用相同的方法。
存储 GCD 的值。
为 GCD 构建给定范围:
对于每个可能的查询,将存在的树的两半向左和向右移动。
当给定范围与一半重叠时;它返回节点。
当它位于给定范围之外时,立即返回 0。
对于部分重叠,遍历并按照以下方法获取返回值。
示例
import java.io.*;
public class tutorialspointGCD{
private static int[] segTree;
public static int[] buildSegmentTree(int[] arr){
int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
int size = 2*(int)Math.pow(2, height)-1;
segTree = new int[size];
SegementTree(arr, 0, arr.length-1, 0);
return segTree;
}
public static int SegementTree(int[] arr, int startNode,int endNode, int si){
if (startNode==endNode) {
segTree[si] = arr[startNode];
return segTree[si];
}
int mid = startNode+(endNode-startNode)/2;
segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
SegementTree(arr, mid+1, endNode, si*2+2));
return segTree[si];
}
private static int gcd(int a, int b){
if (a < b){
int temp = b;
b = a;
a = temp;
}
if (b==0)
return a;
return gcd(b,a%b);
}
public static int findRangeGcd(int startNode, int endNode, int[] arr){
int n = arr.length;
if (startNode<0 || endNode > n-1 || startNode>endNode)
throw new IllegalArgumentException("Invalid arguments");
return findGcd(0, n-1, startNode, endNode, 0);
}
public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si){
if (startNode>endQuery || endNode < startQuery)
return 0;
if (startQuery<=startNode && endQuery>=endNode)
return segTree[si];
int mid = startNode+(endNode-startNode)/2;
return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
}
public static void main(String[] args)throws IOException{
int[] a = {10, 5, 18, 9, 24};
buildSegmentTree(a);
int l = 0, r = 1;
System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
l = 2;
r = 4;
System.out.println("Greatest Common Divisor is here. Please collect the data: "+findRangeGcd(l, r, a));
l = 0;
r = 3;
System.out.println("Greatest Common Divisor is here s . Please collect the data: "+findRangeGcd(l, r, a));
}
}
输出
Greatest Common Divisor is here. Please collect the data: 5 Greatest Common Divisor is here. Please collect the data: 3 Greatest Common Divisor is here s . Please collect the data: 1
结论
在今天的这篇文章中,我们使用特定的编程环境开发了一些可能的代码。通过这些编码逻辑和提到的算法,我们学会了如何正确地找出数组中给定索引范围的 GCD。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

