Как найти пару чисел в списке с заданным диапазоном?

Question

Проблема заключается в следующем:

, учитывая массив из N чисел, найдите два числа в массиве так, чтобы они имели диапазон (max -min) значение K .

например:

вход:

5 3
25 9 1 6 8

вывод:

9 6

Пока что я попробовал сначала отсортировать массива затем найти два дополнительных числа, используя вложенный цикл.Однако, поскольку это своего рода метод грубой силы, я не думаю, что он настолько эффективен, как другие возможные способы.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int count = 0;
        int a, b;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(Math.max(arr[i], arr[j]) - Math.min(arr[i], arr[j]) == k) {
                    a = arr[i];
                    b = arr[j];
                }
            }
        }
        System.out.println(a + " " + b);
    }
}

Очень признателен, если решение было в коде (на любом языке).

Answer 1

Вот код на Python 3, который решает вашу проблему.Это должно быть легко понять, даже если вы не знаете Python.

Эта процедура использует вашу идею сортировки массива, но я использую две переменные left и right (которые определяют два места вмассив), где каждый делает только один проход через массив.Поэтому, кроме сортировки, эффективность моего кода по времени составляет O(N).Сортировка делает всю рутину O(N log N).Это лучше, чем ваш код, который равен O(N^2).

. Я никогда не использую введенное значение N, поскольку Python может легко обрабатывать фактический размер массива.Я добавляю дозорное значение в конец массива, чтобы сделать внутренние короткие циклы проще и быстрее.Это включает в себя еще один проход через массив для вычисления значения часового, но это мало увеличивает время выполнения.Можно уменьшить количество обращений к массиву за счет еще нескольких строк кода - я оставлю это вам.Я добавил подсказки ввода, чтобы помочь моему тестированию - вы можете удалить их, чтобы приблизить мои результаты к тому, что вы, кажется, хотите.Мой код сначала печатает большее из двух чисел, затем меньшее, что соответствует вашему примеру вывода.Но вы, возможно, хотели, чтобы порядок двух чисел соответствовал порядку в исходном несортированном массиве - если это так, я также позволю вам справиться с этим (я вижу несколько способов сделать это).

# Get input
N, K = [int(s) for s in input('Input N and K: ').split()]
arr = [int(s) for s in input('Input the array: ').split()]

arr.sort()
sentinel = max(arr) + K + 2
arr.append(sentinel)
left = right = 0
while arr[right] < sentinel:
    # Move the right index until the difference is too large
    while arr[right] - arr[left] < K:
        right += 1
    # Move the left index until the difference is too small
    while arr[right] - arr[left] > K:
        left += 1
    # Check if we are done
    if arr[right] - arr[left] == K:
        print(arr[right], arr[left])
        break