Найти растущие триплеты, такие, что сумма меньше или равна к

Question

Более простая или популярная версия этой проблемы - найти тройки с заданной суммой. Но этот ставит дополнительное условие. Найти все триплеты в несортированном массиве так, чтобы

d[i]+d[j]+d[k] <= t;   & d[i]<d[j]<d[k] where i<j<k

Это решение первой части проблемы. Но кто-то может предложить, как мы можем расширить его, чтобы включить второе условие. Единственный способ, о котором я могу подумать, - это создать собственную структуру данных при сортировке, чтобы сохранить исходный индекс элемента, а также число. И затем проверка порядка индексов для каждого триплета, возвращаемого алгоритмом, упомянутым во включенной ссылке.

Answer 1

Найдите растущие триплеты, такие, что сумма меньше или равна k:

# include <stdio.h>
void find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;
    for (int i = 0; i < arr_size-2; i++){
       for (int j = i+1; j < arr_size-1; j++){         
           for (int k = j+1; k < arr_size; k++){
               if (A[i] + A[j] + A[k] <= sum)
                 printf("Triplet is %d, %d, %d\n", A[i], A[j], A[k]);
            }
        }
     }
}
int main()
{
    int A[] = {1, 2, 3, 4, 6};
    int sum = 8;
    int arr_size = sizeof(A)/sizeof(A[0]);
    find3Numbers(A, arr_size, sum);
    return 0;
}

Выход:

Execution :
arr_size = 5
Step:1   i=0 and i<3 (arr_size-2)
                                j=1 and j<4 (arr_size-1)
                                                k=2 and k<5 (arr_size)
                                                                A[0]+A[1]+A[2]<=sum --> 1+2+3 <=8 --> 6<=8 ( true )
                                                k=3 and k<5
                                                                A[0]+A[1]+A[3]<=sum --> 1+2+4 <=8 --> 7<=8 ( true )
                                                k=4 and k<5
                                                                A[0]+A[1]+A[4]<=sum --> 1+2+6 <=8 --> 9<=8 ( false )
                                j=2 and j<4
                                                k=3 and k<5
                                                                A[0]+A[2]+A[3]<=sum --> 1+3+4 <=8 --> 8<=8 ( true )
                                                k=4 and k<5
                                                                A[0]+A[2]+A[4]<=sum --> 1+3+6 <=8 --> 10<=8 ( false )
                                j=3 and j<4
                                                k=4 and k<5
                                                                A[0]+A[3]+A[4]<=sum --> 1+4+6 <=8 --> 11<=8 ( false )
                                j=4 and j<4 (false)
Step:2  i=1 and i<3
                                j=2 and j<4
                                                k=3 and k<5
                                                                A[1]+A[2]+A[3]<=sum --> 2+3+4 <=8 --> 9<=8 ( false )
                                                k=4 and k<5
                                                                A[1]+A[2]+A[4]<=sum --> 2+3+6 <=8 --> 11<=8 ( false )
                                j=3 and j<4
                                                k=4 and k<5
                                                                A[1]+A[3]+A[4]<=sum --> 2+4+6 <=8 --> 12<=8 ( false )
                                j=4 and j<4 (false)
Step:3 i=2 and i<3
                                j=3 and j<4
                                                k=4 and k<5
                                                                A[2]+A[3]+A[4]<=sum --> 3+4+6 <=8 --> 13<=8 ( false )
                                j=4 and j<4 (false)
Step:4 i=3 and i<3 (false)

Answer 2

Прежде всего, стоит отметить, что сложность наихудшего случая не может быть лучше, чем O(n^3)потому что в худшем случае есть O(n^3) триплетов, и, очевидно, вам нужно как минимум постоянное время для каждого триплета, чтобы сохранить / распечатать его. И там очень просто и очевидно O(n^3) алгоритм.

При этом, вот как вы можете сделать это со сложностью O(n^2 log n + k), где k это размер ответа. (Хотя @saadtaame утверждает, что имеет ту же сложность, у него есть проблема в его оценке, см. Комментарии ниже его ответа).

Прежде всего, давайте исправим один элемент, скажем, a[i], Теперь давайте создадим новый массив b состоящий из всех элементов из aчто оба имеют индекс больше i и значение больше чем a[i], Теперь проблема сводится к поиску двух индексов j а также k в bтакой, что j < k а также b[j] < b[k],

Для этого мы можем использовать какой-то сортированный набор, например TreeSet на Яве. Мы будем перебирать все возможные значения kподдерживая все элементы с индексами меньше k в TreeSet, Так как TreeSet содержит только элементы с индексами меньше k (из-за того, как мы его строим), и больше, чем i (так как b только содержит такие элементы), и сортируется, то каждый элемент q в этом TreeSet это имеет значение меньше, чем b[k] формирует ответ тройной (a[i], q, b[k]), Вот псевдокод:

for i from 0 to size(a):
    b = empty array
    for j from i + 1 to size(a):
        if a[j] > a[i]:
            add a[j] to b
    treeSet = new TreeSet
    for k from 0 to size(b):
        for each element 'e' in the treeSet in sorted order: // (1)
            if e >= b[k] or a[i] + e + b[k] > t:
                break
            add (a[i], e, b[k]) to the answer // (2)
        add b[k] to the treeSet // (3)

Здесь, если количество возвращаемых элементов меньше O(n^2 log n)Тогда сложность алгоритма будет O(n^2 log n), Причина в том, что линия (2) выполнен точно k времена, и, следовательно, может быть проигнорировано (и итерации по treeSet имеет линейное время амортизируется по количеству элементов), а остальная часть внутреннего цикла: инициализация итератора в (1) и добавление элемента в treeSet в (3) оба не более O(log n) операции.

РЕДАКТИРОВАТЬ: вот небольшой пример. Допустим, массив a = [5, 3, 7, 9, 8, 1] а также t = 20, затем i первые точки в 5мы ставим все элементы, которые находятся справа от 5 и больше, чтобы b, так b = [7, 9, 8], затем k сделаем три итерации:

1. b[k] = 7, В это время treeSet пуст, поэтому ничего не происходит, и 7 добавляется в treeSet.

2. b[k] = 9, На данный момент TreeSet имеет элемент 7. Он меньше, чем 9, но сумма 5 + 7 + 9 > 20, поэтому мы отказываемся от итерации по treeSet. Мы ставим 9 в TreeSet, в набор теперь содержит (7, 9)

3. b[k] = 8, Перебираем TreeSet. Для элемента 7 оба условия выполнены (7 < 8 and 5 + 7 + 8 <= 20), так (5, 7, 8) добавлен в ответ. Для элемента 9 элемент больше, чем b[k]Итак, мы сломаемся.

Тогда цикл закончился k кончено.

Тогда мы двигаемся i один элемент справа. Содержание b будет точно таким же, а три вышеприведенных шага будут почти одинаковыми, за исключением того, что во время второго шага ответ будет достаточно маленьким, поэтому мы получим (3, 7, 9) а также (3, 7, 8),

Затем, когда мы переходим к следующему i, когда a[i] = 7, массив b будет содержать только два элемента, [9, 8]и никакого ответа не будет.

Я бы порекомендовал написать код на Java с некоторыми результатами отладки и немного поиграть с ним, чтобы лучше понять его.

Answer 3

Я думаю, что это можно решить за время O(n^2logn), используя концепцию TreeMap или Sorted Map. Я попытался реализовать то же самое на Java, но концепция осталась прежней.

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        int arr[]={1,2,3,3,4,4,9,10,11,342,43};
        int n=arr.length,t=98,cnt=0;
        Arrays.sort(arr);
        for(int k=2;k<n;k++)
        {
            TreeMap<Integer,Integer> ts1=new TreeMap<>();
            for(int j=0;j<k;j++)
            {
                if(arr[j]==arr[k])
                break;
                int i=Math.min(t-arr[k]-arr[j],arr[j]); //try to get the number of elements less than arr[j] and target-arr[k]-arr[j]
                cnt+=(ts1.lowerKey(i)==null?0:ts1.get(ts1.lowerKey(i)));
                
                if(ts1.containsKey(arr[j]))
                ts1.put(arr[j],ts1.get(arr[j])+1);
                else
                {
                    Integer val=ts1.lowerKey(arr[j]);
                    ts1.put(arr[j],1+(val==null?0:ts1.get(val)));
                }
            }
        }
        System.out.println(cnt);
    }
}

Сообщите мне, работает ли это для вас.

Answer 4

Хаха, приятно видеть здесь мой блог. Однако пост, который вы связали, решает d[i]+d[j]+d[k] < t

Я думаю, вы должны четко спросить, отсортирован ли ваш массив, тогда ваша проблема - небольшое расширение Как найти пары, равные определенной сумме в массиве

Так что для вашего случая (с предположением, что массив отсортирован), вы просто должны убедиться, что i, j, k всегда в порядке возрастания.

Таким образом, классический подход день-ночь (то есть, когда j, k движутся навстречу друг другу) с учетом N элементов и цели T, вы можете попробовать:

for (int i = 0; i < N, i++) {
    int j = i;
    int k = N-1;
    while (j < k) {
        int currSum = i+j+k;
        if (currSum < T) { // increase sum
            j++;
        }
        else if (currSum > T) { // decrease sum
            k--;
        }
        else {
            System.out.println("Found triple: " + i + ", " + j + ", " + k);
            j++;
        }
    }
}

// i, j, k гарантированно будут в порядке возрастания.

Если массив не отсортирован, вы можете просто выполнить оптимизированную перебор. Так что найдите все i, j такие, что d[i]

Answer 5

Я думаю, что вы можете сделать немного лучше, чем O(n^2 log n + k).

Предположим, вы находитесь в положении я. Все элементы до i (1...i) хранятся в одном BST, а все элементы после i (1+1...n) сохраняются во втором BST.

В первом дереве найдите наименьший элемент A[j] такой, что A[j]

Теперь во втором дереве найдите самый большой элемент A [k] такой, что A [k]

Посреди всего этого сделайте дополнительное сравнение. Пусть A[j1] = next(A[j]) (т. Е. A[j1] - следующий элемент в отсортированной последовательности). Если для ak, если оно также следует условиям A[j1]+A[i]+A[k] <=t, запишите такое наибольшее k. И в следующей итерации вместо двоичного поиска используйте это k напрямую.

Сначала начните с i=2, firstTree={A[1]}, secondTree = {A[3]..A[n]}. И всякий раз, когда вы увеличиваете A [i], добавляйте A [i] к первому дереву и удаляйте A[i+1] из второго дерева.

Общая сложность времени: O(n^2+n*log(n)) + O(p) = O(n^2+p), где p - общее количество результатов.

Алгоритм:

Initialization: firstTree={A[1]}, secondTree = {A[3]..A[n]}

For i = 2:(n-1) do:
    j = getFirst(firstTree)
    firstIter = true;
    while(true)
        if A[j]>=A[i] or A[j]+A[i]>t break
        if firstIter:
            k = binSearch(secondTree, t - A[i] -A[j])
            firstIter=false
        else
            if bestk<0:
                break;
            k = bestk
        bestk = -1
        jnext = nextElement(firstTree, A[j]);
        while (A[k]>A[i]):
            print (A[j], A[i], A[k])
            if bestk<0 and A[i]+A[jnext]+A[k] < t:
                bestk = k;
            k = prevElement(secondTree, A[k])
    Add(firstTree, A[i])
    Remove(secondTree, A[i+1])

Обратите внимание, что binSearch вызывается только один раз для i, а для i i nextElement проходит по дереву ровно один раз (сложность O(n)). Внутренний цикл while вызывается ровно один раз. Таким образом, общая сложность равна O(n^2 + nlogn + p), где p - количество выходов.

РЕДАКТИРОВАТЬ: Так как, если мы найдем бесплодный j (то есть, нет решения для j), мы остановимся. Я думаю, что эта стоимость включена в саму O (p). Таким образом, последняя сложность - O(nlogn + p). Извините, у меня нет времени, чтобы предоставить подробные доказательства.

Answer 6

Вот версия c++

      #include <bits/stdc++.h>
using namespace std;

vector<int> helper(vector<int> &A, int T)
{
    vector<int> ans;
    int N = A.size();
    for (int i = 0; i < N; i++)
    {
        vector<int> B;
        for (int j = i + 1; j < N; j++)
        {
            if (A[j] > A[i])
                B.push_back(A[j]);
        }
        set<int> S;
        set<int>::iterator it;
        for (int k = 0; k < B.size(); k++)
        {
            for (auto it = S.begin(); it != S.end(); it++)
            {
                int sum = A[i] + *it + B[k];
                if (*it >= B[k] || sum > T)
                    break;
                cout << A[i] << " - " << *it << " - " << B[k] << endl;
                ans.push_back(sum);
            }
            S.insert(B[k]);
        }
    }
    return ans;
}

vector<int> helper1(vector<int> &A, int T)
{
    vector<int> ans;
    int N = A.size();
    for (int i = 0; i < N - 2; i++)
    {
        for (int j = i + 1; j < N - 1; j++)
        {
            for (int k = j + 1; k < N; k++)
            {
                int sum = A[i] + A[j] + A[k];
                if (sum <= T && A[i] < A[j] && A[j] < A[k])
                {
                    cout << A[i] << " - " << A[j] << " - " << A[k] << endl;
                    ans.push_back(sum);
                }
            }
        }
    }
    return ans;
}

void print(vector<int> &A)
{
    for (int a : A)
        cout << a << " ";
    cout << endl;
}

int main()
{
    vector<int> A({1, 4, 12, 3, 6, 10, 14, 3});
    int T = 11;
    vector<int> ans = helper(A, T); // O(n^2log n)
    print(ans);
    vector<int> ans1 = helper1(A, T); // )(n^3)
    print(ans1);
    return 0;
}

Answer 7

Я думаю, что n^2*logn может быть достигнуто в этом случае.

Что нам нужно сделать, так это сначала отсортировать по быстрой сортировке чисел, чтобы избежать лишнего цикла и по умолчанию i

Моя логика: d [i] + d [j] + d [k] <= t, поэтому d [k] <= t - d [i] -d [j], поэтому первый цикл будет выполняться с 1 по n, второй - от i + 1 до n, а для третьего мы сделаем бинарный поиск (t - d[i] -d[j]) и сравним для d [i]

Итак, мой звонок:

    Arrays.sort(d);
    for (int i = 0; i < d.length; i++) {
        for (int j = i + 1; j < d.length; j++) {
            int firstNumber = d[i];
            int secondNumber = d[j];
            int temp = t - firstNumber - secondNumber;
            if ((firstNumber < secondNumber) && (secondNumber < temp))  {
                int index = Arrays.binarySearch(d, temp);
                    if (index >= 0) {
                    ......
                    }
                }
            }
        }
    }

Answer 8

С условием, где i<j<kполовина вашего куба не подходит, так что вы можете устранить то, что не требуется

for (int k = 0; k < N, k++) 
{
    for (int j = 0; j < k, k++) 
    {       
                if (d[j] < d[k]) continue;
        for (int i = 0; i < j, i++) 
        {
            if (d[k] < d[j]) continue;
            if (d[i]+d[j]+d[k] <= t) 
            {
                 //valid result
            }
        }
    }
}

Answer 9

Если вы исправите i и j, вам нужно будет найти число в массиве, которое меньше или равно t - d[i] - d[j], Сохраните вторую версию вашего массива, в котором каждый элемент также хранит свой индекс. Сортируйте этот массив в порядке возрастания.

Теперь для всех пар i, j с i < j (это всего лишь два вложенных цикла), вы бинарный поиск t - d[i] - d[j]; если такое число существует, вы перебираете все числа слева до этого числа и проверяете, что их индексы больше, чем j, если это так, вы добавляете к выводу. Сложность O(n*n*lg n + k) где k - количество выходов, которые удовлетворяют условию.

РЕДАКТИРОВАТЬ: первый пост ОП был = теперь он изменился на <=, Я обновил свой ответ.