倍增算法（也称为指数跳跃算法）是一种高效的算法，用于解决一些特定的查找问题，例如在数组中查找某个区间内的最小值或最大值。以下是一个倍增算法的Java代码示例，用于解决查找最小值的问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public class SparseTable {
static int[][] sparseTable;
public static void buildSparseTable(int[] arr) {
int n = arr.length;
int logN = (int) (Math.log(n) / Math.log(2)) + 1;
sparseTable = new int[n][logN];
for (int i = 0; i < n; i++) {
sparseTable[i][0] = arr[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
sparseTable[i][j] = Math.min(sparseTable[i][j - 1], sparseTable[i + (1 << (j - 1))][j - 1]);
}
}
}
public static int queryMin(int left, int right) {
int j = (int) (Math.log(right - left + 1) / Math.log(2));
return Math.min(sparseTable[left][j], sparseTable[right - (1 << j) + 1][j]);
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
buildSparseTable(arr);
int left = 2;
int right = 5;
int minInRange = queryMin(left, right);
System.out.println("Minimum element in range [" + left + ", " + right + "]: " + minInRange);
}
}
|
在这个示例中，buildSparseTable 方法构建了一个稀疏表，用于在数组中查询指定范围内的最小值。queryMin 方法用于查询指定范围内的最小元素。这种方法的时间复杂度为O(1)查询，但需要O(n log n)的预处理时间和O(n log n)的空间。
倍增算法在一些特定的查找问题中非常有用，如查找最小值、最大值等。但请注意，它适用于不会频繁修改数组内容的情况，因为构建稀疏表的开销较大。