1
给定一个数组，我需要找出最近的非互质数的指数（即GCD（Ai，Aj）> 1，对于阵列中的任何Ai和Aj，i！= j）例如，让该阵列是查找最近的非互质数
[2 17 4 6 10]
答案将是
[3 -1 4 3 4]
我写此蛮力代码（其是O（n^2）），使用二进制GCD方法，这是不非常有效。我想知道是否有更快的方法来做到这一点。 特别是在O（NlogN）
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author Mayur Kulkarni
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
BladeReader in = new BladeReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
GCDPuz solver = new GCDPuz();
solver.solve(1, in, out);
out.close();
}
static class GCDPuz {
public static int gcd(int p, int q) {
if (q == 0) return p;
if (p == 0) return q;
// p and q even
if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;
// p is even, q is odd
else if ((p & 1) == 0) return gcd(p >> 1, q);
// p is odd, q is even
else if ((q & 1) == 0) return gcd(p, q >> 1);
// p and q odd, p >= q
else if (p >= q) return gcd((p - q) >> 1, q);
// p and q odd, p < q
else return gcd(p, (q - p) >> 1);
}
public int coprime(int p, int q) {
if (p % 2 == 0 && q % 2 == 0) {
return 2;
} else if (p == q + 1 || q == p + 1) {
return 1;
} else {
return gcd(p, q);
}
}
public void solve(int testNumber, BladeReader in, PrintWriter out) {
int size = in.nextInt();
int[] arr = in.readIntArray(size);
int[] ans = new int[size];
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
ans[i] = -1;
continue;
}
int left = i == 0 ? -1 : findLeft(arr, i);
int right = i == arr.length - 1 ? -1 : findRight(arr, i);
int leftDist = left == -1 ? -1 : i - left;
int rightDist = right == -1 ? -1 : right - i;
int anss = findNearestIndex(left, leftDist, right, rightDist);
ans[i] = anss == -1 ? -1 : anss + 1;
}
printa(ans, out);
}
private void printa(int[] ans, PrintWriter out) {
StringBuilder sb = new StringBuilder();
for (int an : ans) {
sb.append(an).append(" ");
}
out.println(sb.toString());
}
private int findRight(int[] arr, int i) {
if (arr[i] == -1) return -1;
for (int j = i + 1; j < arr.length; j++) {
if (coprime(arr[i], arr[j]) > 1) return j;
}
return -1;
}
private int findLeft(int[] arr, int i) {
if (arr[i] == -1) return -1;
for (int j = i - 1; j >= 0; j--) {
if (coprime(arr[i], arr[j]) > 1) return j;
}
return -1;
}
private int findNearestIndex(int one, int oneDist, int two, int twoDist) {
if (oneDist == -1 && twoDist == -1) return -1;
if (oneDist == -1) return two;
if (twoDist == -1) return one;
if (oneDist == twoDist) {
return Math.min(one, two);
}
return oneDist < twoDist ? one : two;
}
}
static class BladeReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public BladeReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public int[] readIntArray(int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = nextInt();
}
return array;
}
}
}
我投票结束这个问题作为题外话，因为它属于[codereview.se] –
@JimGarrison它也被标记算法，它不仅是OP想要建议的代码。 –
OP提供了示例代码 - 我们让人们去做 - 但问题是关于算法的问题，而不是代码。如果gcd（a，b）> 1或gcd（a，c）> 1，那么我们可以利用gcd（a，b * c）> 1的事实吗？我听说过这个技巧被用在因式分解算法中，但是看看这些数字我不明白它在这里可以得到怎样的回报--gCD的成本似乎上升得太快，因为数字中的数字位数被分解了增加。如果我错了，它可能有助于生成一个二叉树，其中节点上的数字是其下面叶子中所有数字的乘积。 – mcdowella