Нахождение двух конкретных чисел в огромных массивах - PullRequest
Новая
       11

Нахождение двух конкретных чисел в огромных массивах

0 голосов
/ 21 декабря 2018

В настоящее время я пытаюсь решить проблему с алгоритмом, и из-за того, что я новичок в программировании, я чувствую, что не смогу разобраться без каких-либо предварительных знаний.Мое намерение состоит не в том, чтобы получить ответ на проблему, а в рекомендации по обработке огромных массивов в Java.

Проблема в том, что вы получаете число (3> n <200.000), а затем получаете отсортированный массив чисел, которыеимеет длину n, а затем вы получите другое число (n2) (все числа могут быть сохранены целым числом). </p>

Вам нужно найти два числа в массиве, чтобы их сумма составила n2-n.

Вы всегда будете иметь правильный ответ и всегда будете двумя числами.

Например: 3 1 2 3 3 Ответ будет 1 и 2, потому что 6 - 3 = 3;

Мой код работает, но он превышает время и потребление памяти.Поэтому я ищу кого-то, кто расскажет о лучших способах поиска этих чисел, которые также могут быть полезны для улучшения моих алгоритмов.

Я до сих пор суммировал все числа в массиве и получил n2 - n;затем создайте два индекса, первый 0 и второй (n2 - n) - 1;Затем выполните цикл, пока первый индекс меньше второго индекса.Во время цикла выполняется двоичный поиск первого индекса и второго индекса.Если двоичный поиск находит оба числа, верните их в качестве ответа. 

public static BufferedReader br;
public static int numHechizos;
public static String line;
public static String[] split;
public static int damage;
public static int[] hechizos;

public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));

    numHechizos = Integer.parseInt(br.readLine());

    while (numHechizos != 0){
        caso(numHechizos);
        numHechizos = Integer.parseInt(br.readLine());
    }
}

public static void caso(int numHechizos) throws IOException {
    line = br.readLine();
    split = line.split(" ");
    damage = Integer.parseInt(br.readLine());

    int sum = 0;
    hechizos = new int[numHechizos];
    for (int i = 0; i < numHechizos; i++) {
        int num = Integer.parseInt(split[i]);
        hechizos[i] = num;
        sum += num;
    }

    int find = sum - damage;
    int n1 = 1; int n2 = find - 1;
    while (n1 < n2){
        int bn1 = Arrays.binarySearch(hechizos, n1);
        int bn2 = Arrays.binarySearch(hechizos, n2);

        if (bn1 > -1 && bn2 > -1){
            System.out.println(n1 + " " + n2);
            break;
        }
        n1++;
        n2--;
    }

    System.gc();
}
...