1
Учитывая массив, мне нужно найти индексы ближайшего несовпадающего числа (т.е. GCD (Ai, Aj)> 1 для любых Ai и Aj в массиве, i! = J) Например, пусть массив будетПоиск ближайшего несовместимого числа
[2 17 4 6 10]
ответ будет
[3 -1 4 3 4]
Я написал этот перебор код (который является O (N^2)), используя метод Binary НОД, который не является очень эффективный. Мне интересно, есть ли более быстрый способ сделать это. Особенно в 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 предоставил пример кода, который мы просим людей делать, но вопрос заключается в алгоритмах, а не в коде. Можем ли мы воспользоваться тем фактом, что если gcd (a, b * c)> 1, если gcd (a, b)> 1 или gcd (a, c)> 1? Я слышал об этом трюке, который используется в алгоритмах факторизации, но, глядя на цифры, я не вижу, как это можно окупить здесь - стоимость gcd, похоже, растет слишком быстро, так как количество цифр в числах, которые должны быть факторизованы увеличивается. Если я ошибаюсь, это может помочь создать двоичное дерево, в котором число в узлах является произведением всех чисел в листьях ниже него. – mcdowella