Поиск пар с продуктом больше суммы

Ответ 1

Вот алгоритм O(n).

Посмотрим на A * B >= A + B.

• Когда A, B <= 0, оно всегда верно.

• Когда A, B >= 2, это всегда верно.

• Когда A >= 1, B <= 1 (или B >= 1, A <= 1), оно всегда ложно.

• Когда 0 < A < 1, B < 0 (или 0 < B < 1, A < 0), оно может быть истинным или ложным.

• Когда 1 < A < 2, B > 0 (или 1 < B < 2, A > 0), оно может быть истинным или ложным.

Здесь визуализация, любезно предоставлена ​​Wolfram Alpha и Geobits:

Теперь, на алгоритм.

* Чтобы найти пары, где одно число находится между 0 и 1 или 1 и 2, я делаю что-то похожее на то, что сделано для проблема 3SUM.

* "Pick 2" здесь относится к combinations.

• Подсчитайте все пары, в которых оба отрицательные

  Сделайте двоичный поиск, чтобы найти индекс первого положительного ( > 0) числа - O(log n).

  Так как у нас есть индекс, мы знаем, сколько чисел отрицательно/нулевое, нам просто нужно выбрать 2 из них, так что amountNonPositive * (amountNonPositive-1) / 2 - O(1).

• Найдите все пары, в которых один находится между 0 и 1

  Сделайте бинарный поиск, чтобы найти индекс последнего числа < 1 - O(log n).

  Начните с этого индекса как правый индекс и самый левый элемент в качестве левого индекса.

  Повторите это, пока правый индекс <= 0: (работает в O(n))

  • Пока произведение меньше суммы, уменьшите левый индекс

  • Подсчитайте все элементы, превышающие левый индекс

  • Уменьшить правый индекс

• Найдите все пары, в которых один находится между 1 и 2

  Сделайте двоичный поиск, чтобы найти индекс первого числa > 1 - O(log n).

  Начните с этого индекса как левого индекса и самого правого элемента в качестве правого индекса.

  Повторяйте это, пока левый индекs >= 2: (работает в O(n))

  • Пока произведение больше суммы, уменьшите правый индекс

  • Подсчитайте все элементы, превышающие правый индекс

  • Увеличить левый индекс

• Подсчитайте все пары с двумя номерами >= 2

  В конце последнего шага мы находимся в первом индексе >= 2.

  Теперь, оттуда, нам просто нужно выбрать 2 всех остальных чисел,
  так что снова amountGreaterEqual2 * (amountGreaterEqual2-1) / 2 - O(1).

Ответ 2

Вы можете найти и распечатать пары (в сокращенной форме) в O(n log n).

Для каждого A[i] существует минимальное число k, которое удовлетворяет условию (1). Все значения, превышающие k, также будут удовлетворять условию.

Поиск самого низкого j, для которого A [j] >= k, использующий двоичный поиск O(log n).

Итак, вы можете найти и распечатать результат следующим образом:

(i, j)
(1, no match)
(2, no match)
(3, >=25)
(4, >=20)
(5, >=12)
(6, >6)
(7, >7)
...
(n-1, n)       

Если вы хотите распечатать все комбинации, то это O (n ^ 2), так как число комбинаций - O (n ^ 2).

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

Ответ 3

Здесь двоичный поиск, O (n log n):

Там точка прерывания для каждого номера в A*B = A+B. Вы можете уменьшить это до B = A / (A - 1). Все номера с одной стороны или другой будут соответствовать этому. Не имеет значения, есть ли отрицательные числа и т.д.

• Если A < 1, то все числа <= B соответствуют.

• Если A > 1, то все числа >= B соответствуют.

• Если A == 1, то нет совпадения (разделите на ноль).

(ссылка Wolfram Alpha)

Итак, некоторый псевдокод:

loop through i
    a = A[i]
    if(a == 1)
        continue
    if(a >= 2)
        count += A.length - i 
        continue

    j = binsearch(a / (a-1))

    if(j <= i)
        continue

    if(a < 1)
        count += j-i
    if(a > 1)
        count += A.length - j

Ответ 4

Здесь a O(n) алгоритм, который решает проблему, когда элементы массива положительны.

Когда элементы положительны, мы можем сказать, что:

• Если A[i]*A[j] >= A[i]+A[j], когда j>i, то A[k]*A[j] >= A[k]+A[j] для любого k, который удовлетворяет k>i (потому что массив отсортирован).

• Если A[i]*A[j] < A[i]+A[j], когда j>i, то A[i]*A[k] < A[i]+A[k] для любого k, удовлетворяющего k<j.

(эти факты не сохраняются, когда оба числа являются дробями, но тогда условие не будет выполнено)

Таким образом, мы можем выполнить следующий алгоритм:

int findNumOfPairs(float A[])
{    
    start = 0;
    end = A.length - 1;
    numOfPairs = 0;

    while (start != end)
    {
        if (A[start]*A[end] >= A[start]+A[end])
        {
            numOfPairs += end - start;
            end--;
        }
        else
        {
            start++;
        }
    }

    return numOfPairs;
}

Ответ 5

Как насчет исключения всех поплавков, которые меньше 1.0, так как любое число с числом меньше 1, x * 0,3 = A [i] + A [j] для каждого я < j, поэтому нам нужно только подсчитать числа массива для вычисления числа пар (i, j), мы можем использовать формулу о перестановке и комбинации для ее вычисления. формула должна быть n (n-1)/2.