Определить, существуют ли в множестве S два элемента, чья сумма является точно x - правильным решением?

Question

взято из введения в алгоритмы

Опишите алгоритм времени Θ (n lg n) что, учитывая набор S из n целых чисел и другое целое число х, определяет, является ли или не существует двух элементов в S чья сумма ровно х.

Это мое лучшее решение, реализованное в Java на данный момент:

    public static boolean test(int[] a, int val) {
    mergeSort(a);

    for (int i = 0; i < a.length - 1; ++i) {
        int diff = (val >= a[i]) ? val - a[i] : a[i] - val;

        if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
            return true;
        }
    }

    return false;
}

Теперь мой первый вопрос: правильное ли это решение? Насколько я понимаю, mergeSort должен выполнять сортировку по O (n lg n), цикл должен принимать O (n lg n) (n за итерацию, умноженную на O (lg n), для двоичного поиска, что приводит к O (2n lg). n), так что это должно быть правильно.

Мой второй вопрос: есть ли лучшие решения? Важна ли сортировка массива?

Answer 1

Ваше решение в порядке. Да, вам нужно отсортировать, потому что это обязательное условие для бинарного поиска. Вы можете внести небольшие изменения в свою логику следующим образом:

public static boolean test(int[] a, int val) 
{
    Arrays.sort(a);

    int i = 0;            // index of first element.
    int j = a.length - 1; // index of last element. 

    while(i<j)
    {
        // check if the sum of elements at index i and j equals val, if yes we are done.
        if(a[i]+a[j] == val)
            return true;
        // else if sum if more than val, decrease the sum.
        else if(a[i]+a[j] > val)
            j--;
        // else if sum is less than val, increase the sum.
        else
            i++;
    }
    // failed to find any such pair..return false. 
    return false;
}

Answer 2

Есть еще одно очень быстрое решение: представьте, что вам нужно решить эту проблему в Java примерно за 1 млрд. Целых чисел. Вы знаете, что в Java целые числа идут от -2**31+1 до +2**31.

Создание массива с 2**32 миллиардами бит (500 МБ, тривиально на современном оборудовании).

Итерация по вашему набору: если у вас есть целое число, установите соответствующий бит в 1.

O (n) пока.

Повторите итерацию по вашему набору: для каждого значения проверьте, установлен ли у вас бит "current val - x".

Если он у вас есть, вы возвращаете true.

Конечно, ему нужно 500 МБ памяти.

Но это должно обойти любое другое решение O (n log n), если, скажем, вам нужно решить эту проблему с 1 миллиардом целых чисел.

О (п).

Answer 3

1. Это правильно; Ваш алгоритм будет работать за O (n lg n).

2. Есть лучшее решение: ваша логика для вычисления различий неверна. Независимо от того, a[i] больше или меньше val, вам все равно нужно diff, чтобы быть val - a[i].

Answer 4

Вот решение O (n) с использованием хэш-набора:

  public static boolean test(int[] a, int val) {
      Set<Integer> set = new HashSet<Integer>();

      // Look for val/2 in the array
      int c = 0;
      for(int n : a) {
        if(n*2 == val)
          ++c
      }
      if(c >= 2)
         return true; // Yes! - Found more than one

      // Now look pairs not including val/2
      set.addAll(Arrays.asList(a));
      for (int n : a) {
         if(n*2 == val)
            continue;
         if(set.contains(val - n))
            return true;
      }

      return false;
   }

Answer 5

Простое решение, после сортировки, переместить указатели вниз с обоих концов массива, ища пары, которые суммируются с x. Если сумма слишком велика, уменьшите указатель вправо. Если слишком низкий, увеличьте левую. Если указатели пересекаются, ответ - нет.

Answer 6

Думаю, я обнаружил небольшую ошибку в вашей реализации, но тестирование должно быстро ее выявить.

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

int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
    while (a[i] + a[j] > val) {
        j--;
    }
    if (a[i] + a[j] == val) {
        // heureka!
    }
}

Этот шаг O (n). (Доказательство того, что это оставлено для вас в качестве упражнения.) Конечно, весь алгоритм все еще принимает O (n log n) для сортировки слиянием.

Answer 7

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

Answer 8

Вот альтернативное решение, добавив еще несколько условий в mergesort.

public static void divide(int array[], int start, int end, int sum) {

    if (array.length < 2 || (start >= end)) {
        return;
    }
    int mid = (start + end) >> 1; //[p+r/2]
    //divide
    if (start < end) {
        divide(array, start, mid, sum);
        divide(array, mid + 1, end, sum);
        checkSum(array, start, mid, end, sum);
    }
}

private static void checkSum(int[] array, int str, int mid, int end, int sum) {

    int lsize = mid - str + 1;
    int rsize = end - mid;
    int[] l = new int[lsize]; //init
    int[] r = new int[rsize]; //init

    //copy L
    for (int i = str; i <= mid; ++i) {
        l[i-str] = array[i];
    }
    //copy R
    for (int j = mid + 1; j <= end; ++j) {
        r[j - mid - 1] = array[j];
    }
    //SORT MERGE
    int i = 0, j = 0, k=str;
    while ((i < l.length) && (j < r.length) && (k <= end)) {
    //sum-x-in-Set modification
    if(sum == l[i] + r[j]){
        System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + r[j]);            
    }
     if (l[i] < r[j]) {
            array[k++] = l[i++];
        } else {
            array[k++] = r[j++];
        }
    }
    //left over
    while (i < l.length && k <= end) {
        array[k++] = l[i++];
          //sum-x-in-Set modification
        for(int x=i+1; x < l.length; ++x){
            if(sum == l[i] + l[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + l[x]);
            }
        }
    }
    while (j < r.length && k <= end) {
        array[k++] = r[j++];
          //sum-x-in-Set modification
        for(int x=j+1; x < r.length; ++x){
            if(sum == r[j] + r[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + r[j] + " " + r[x]);
            }
        }
    }
}

Но сложность этого алгоритма все еще не равна THETA (nlogn)