Блог

Главная - Вопросы по программированию - Ближайшая сумма пар к x в двух отсортированных массивах

Ближайшая сумма пар к x в двух отсортированных массивах

#java #algorithm

Вопрос:

Я столкнулся с проблемой кодирования, которая заключается в следующем:

Учитывая 2 отсортированных массива: A и B и положительное целое число x, выведите сумму ближайшей пары (по одной из каждого массива) в x.

Пример:

B = {10,20,30,40} , A = {0,4,6,11,11} , x = 13.

Выходные данные: 4 и 10.

Это то, что я пробовал:

     int i = 0;
    int j = b.length - 1;
    int closest = Integer.MAX_VALUE;
    String s = "";
    while (i <= a.length - 1 amp;amp; j >= 0)
    {
        if (Math.abs((b[j]   a[i]) - x) < closest || Math.abs((b[j]   a[i]) - x) == 0)
        {
            closest = Math.abs(x - (b[j]   a[i]));
            s = a[i]   " "   "and"   " "   b[j];
            if (j != 0)
                j--;
        }
        if (Math.abs((b[j]   a[i]) - x) > closest || j == 0)
            i  ;
    }
    System.out.println(s);

Этот код отлично работает с большинством входов, которые я протестировал, включая приведенный выше пример,
за исключением случаев, когда вход x равен 70, а выход-11 и 30 вместо 11 и 40.

В основном я пытаюсь понять, когда мне следует уменьшать j , а когда увеличивать i , чтобы код работал на каждом возможном x входе.

Решение должно быть O(n) временной сложности.

Спасибо за помощь! (Если вы обнаружите ошибки в моем английском, пожалуйста, дайте мне знать, я пытаюсь исправиться.)

Комментарии:

1.https://www.geeksforgeeks.org/given-two-sorted-arrays-number-x-find-pair-whose-sum-closest-x/ ?

Ответ №1:

Вы должны использовать метод двух указателей, чтобы получить желаемый результат. Приведенный ниже код будет работать для вас.

        while (i <= a.length-1 amp;amp; j >= 0) {
    
            if (Math.abs((b[j] a[i]) - x ) < closest || Math.abs( (b[j] a[i]) - x) == 0) {
                closest = Math.abs(x - (b[j] a[i])) ;
                s = a[i]   " "    "and"   " "   b[j];
            }
            
            if (b[j] a[i] > x) j --;
            else i  ;
        }

Временная сложность определенно O(n).

Для получения подробных инструкций, пожалуйста, посетите веб-сайт GeeksforGeeks.

Ответ №2:

 public static int[] getClosestPairSum(int[] A, int[] B, int x) {
    TreeSet<Integer> unique = new TreeSet<>();

    for (int a : A)
        unique.add(a);

    int absDiff = -1;
    int[] res = { 0, 0 };

    for (int b : B) {
        for (Integer aa : Arrays.asList(unique.floor(x - b), unique.ceiling(x - b))) {
            if (aa == null)
                continue;

            int curAbsDiff = Math.abs(x - b - aa);

            if (absDiff == -1 || curAbsDiff < absDiff) {
                absDiff = curAbsDiff;
                res[0] = aa;
                res[1] = b;
            }
        }
    }

    return res;
}

Ответ №3:

В основном похоже на код вопроса (немного проще?):

 // returning an array so I can check against brute force algorithm
private static int[] closestPair(int[] a, int[] b, int x) {
    int closest = Integer.MAX_VALUE;
    int[] result = { -1, -1 };    // could use null
    int i = 0;
    int j = b.length-1;
    while (i < a.length amp;amp; j >= 0) {
        int diff= (a[i]   b[j]) - x;

        // is it closer?
        if (abs(diff) < closest) {
            closest = abs(diff);
            result[0] = a[i];
            result[1] = b[j];
        }

        // which pointer to change for next iteration
        if (diff == 0) break;  // shortcut, can't get closer
        if (diff < 0) {
            i  ;               // sum was less than x, try higher value
        } else {
            j--;               // sum was greater, try a smaller one
        }
    }
    return resu<
}

Метки: