Как найти 2-сумму за линейное время? - PullRequest
Новая
       12

Как найти 2-сумму за линейное время?

0 голосов
/ 10 июня 2018

Я записался на курс Алгоритмы, часть II на Coursera, и один из вопросов интервью (без оценки) выглядит следующим образом:

2-сумма .Учитывая массив a из n 64-разрядных целых чисел и целевое значение T, определите, существуют ли два различных целых числа i и j, такие что a[i] + a[j] = T.Ваш алгоритм должен работать в линейном времени в худшем случае.

Подсказка: сортируйте массив по линейному времени.

Я могу решить его несколькими способами:

  1. Вставить элементы в хэш-таблицу за один проход.Затем сделайте 2-й проход, ища T - a[i] в хеш-таблице.Сложность пространства составляет O (n) для хэш-таблицы и O (n) для 2 проходов.Это решение соответствует требованию времени, указанному в вопросе.

  2. Сортируйте массив, а затем выполните 2 указателя i и j от начала и конца соответственно, ищаa[i] + a[j] = T.Если a[i] + a[j] < T, увеличить i, иначе уменьшить j.Сложность пространства зависит от алгоритма сортировки;при условии быстрой сортировки, дополнительное пространство не требуется.Сложность времени, nlogn, поэтому она не соответствует требованию времени, указанному в вопросе.

  3. Учитывая, что вопрос задается после лекции по Radix Sort, я предполагаю, что намерение состоит в том, чтобы использовать один из них.Сортов Radix.Поскольку в вопросе указываются 64-разрядные целые числа с использованием двоичного представления long и с использованием сортировки по основанию MSD , массив можно сортировать на месте за линейное время.Это кажется лучшим подходом.

Другие идеи?

PS Я видел этот вопрос , но он предполагает отсортированный массив, ивсе ответы там используют какое-то хеширование.

Я также видел этот вопрос , но он кажется слишком сложным для конкретного случая 2-суммы.

Ответы [ 3 ]

0 голосов
/ 10 июня 2018

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

public static int[] twoSumInOnePass(int[] values, int target) throws Exception {
    // value => index
    Map<Integer, Integer> valueToIndexMap = new HashMap<Integer, Integer>();
    for (int i = 0; i < values.length; i++) {
        int remainder = target - values[i];
        if (valueToIndexMap.containsKey(remainder)) {
            return new int[] { valueToIndexMap.get(remainder), i };
        }
        valueToIndexMap.put(values[i], i);
    }

    throw new Exception("Could not find indexes that sum to " + target);
}

https://leetcode.com/problems/two-sum/description/

0 голосов
/ 11 июня 2018

Отвечая на мой собственный вопрос, вот рабочее решение на Java: 

public class RadixSortsInterviewQuestions {
    private static final int MSB = 64;

    static Map.Entry<Integer, Integer> twoSum(long[] a, long sum) {
        int n = a.length - 1;
        sort(a, MSB, 0, n);

        for (int i = 0, j = n; i < j; ) {
            long t = a[i] + a[j];
            if (t == sum) {
                return new SimpleImmutableEntry<>(i, j);
            } else if (t < sum) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }

    // Binary MSD radix sort: https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations
    private static void sort(long[] a, int d, int lo, int hi) {
        if (hi < lo || d < 1) return;

        int left = lo - 1;
        int right = hi + 1;

        for (int i = left + 1; i < right; ) {
            if (isBitSet(a[i], d)) {
                swap(a, i, --right);
            } else {
                left++;
                i++;
            }
        }
        sort(a, d - 1, lo, left);
        sort(a, d - 1, right, hi);
    }

    private static boolean isBitSet(long x, int k) {
        boolean set = (x & 1L << (k - 1)) != 0;

        // invert signed bit so that all positive integers come after negative ones
        return (k == MSB) != set;
    }

    private static void swap(long[] a, int i, int j) {
        long tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
0 голосов
/ 10 июня 2018

Я проанализировал ваши наблюдения и относительно того, что, кажется, удовлетворяет требованию:

Вставьте элементы в хеш-таблицу за один проход.Затем сделайте 2-й проход, ища T - a [i] в ​​хеш-таблице.Сложность пространства составляет O (n) для хэш-таблицы и O (n) для 2 проходов.Это решение соответствует требованию времени, указанному в вопросе.

Я считаю, что этот подход не соответствует требованиям, поскольку теоретически сложность вставки hashtable для наихудшего случая равна O (n).

Поскольку вы сказали, что изучали сортировку по Radix, я думаю, что это путь, вы можете отсортировать массив в соответствии с требованиями времени, а затем вы можете использовать технику Two Pointers, чтобы проверить, есть ли сумма T: 

int left = 0, right = array_size - 1;
boolean found = false;
while (left < right) {

    if (a[left] + a[right] == T) {              
        found = true;
    }
    else if (a[left] + a[right] < T) {
        left++;
    }
    else {
        right--;
    }
}
...