LINUX.ORG.RU

Вопрос на лучший (быстрейший) алгоритм.


0

0

Есть массив чисел int[] input. Натуральные, в произвольном порядке, количество чисел - N.

Есть число int K, равное константе.

Найти в input все такие пары, суммы которых равны K.

Пример:

int input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4};
int K = 10;

Говорят есть алгоритм ценой O(n).

Пока есть такой алгоритм - составить битовую карту или map всех чисел, или другой объект, у которого можно быстро спрашивать «есть ли такое число».

Затем проходя по всем числам и вычитая их из K (находя второе слагаемое), проверять - есть ли такое слагаемое вообще (это либо O(1) для битовой карты, либо O(log(n)) для дерева бинарного.

То есть имеющийся алгоритм жрёт O(n*log(n)) времени, а есть какой-то O(n).

Может быть входной массив отсортировать (один раз затратив O(n*log(n)) ), далее идти двумя указателями с конца и с начала. Можно с этим что-то придумать?

Может быть входной массив отсортировать (один раз затратив O(n*log(n)) )

Сортировка массива из N небольших целых делается за O(N). Подробнее тут: http://en.wikipedia.org/wiki/Radix_sort

Manhunt ★★★★★ ()

нюбам засрали мозги контейнерами, классами и битовыми полями?? совсем отучились думать :(

решение в-лоб даёт O(n),

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4};
int N=sizeof(input)/sizeof(int);
int K = 10;
void print_pair(int *input,int K) {
        int *mem=alloca(sizeof(int)*K);
        int t,i;
        memset(mem,0,sizeof(int)*K);
        for(t=0;t<N;t++) {
                i=input[t];
                if (i<=0 || i>=K) continue;
                if (mem[K-i]!=0) {
                        printf("%d %d\n",i,K-i);
                        mem[K-i]=0;
                } else
                        mem[i]=1;
        }
}
int main() {
        print_pair(input,K);
        return 0;
}

с обычного С на то что называете С++, перевдёте сами

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

Идею одобряю, имплементация - говно.

anonymous ()

вот кстати вариант без битсета, что лучше подойдет для варианта, где K большое, а входных чисел немного:

[code=cpp]#include <cstdio> #include <unordered_set> #include <vector>

using namespace std;

int main() { const int K = 10; unordered_set<int> s; vector<int> v = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4};

for( int n : v ) { if( s.find( K - n ) != s.end() ) printf( «%d %d\n», n, K - n ); s.insert( n ); } } [/code]

anonymous ()
Ответ на: комментарий от MKuznetsov

Если входные данные генерировать случайным образом (по всему диапазону указанного типа), то, очень вероятно, «решение в лоб» вывалится на переполнении стека (привет, alloca).

ТС как раз таки пытается рассуждать, а не бросается писать код. Логика нормальная для анализа сложности алгоритма. Сортируем за NLogN, далее линейно считаем пары, получаем NLogN. И уж потом можно отметить, что для маленьких натуральных чисел возможна линейная сортировка, и, соответственно линейный алгоритм поиска пар (что и отметил мэнхант). Такие дела.

anonymous ()

Тред не читай, сразу отвечай

#include<iostream>

#define LEN(x) (sizeof(x)/sizeof(x[0]))
//const unsigned input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4,5;
const unsigned input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4,5,1000000-2};
//const unsigned input[] = {-10,20}; //where is my warning, mr GCC?
const unsigned K = 1000000;

int main()
{
	unsigned found[K+1] = {};
	for(const unsigned * i=input;i!=input+LEN(input);++i)
		if (*i<=K)
		{
			if (found[(K-*i)])
				std::cout << "(" << (K-*i) << " ," << *i << ")" << std::endl;
			found[*i]++;
		}
}
legolegs ★★★★★ ()
Ответ на: Тред не читай, сразу отвечай от legolegs

Вообще это конечно всё гонево, про O(n). это O1(n)+O2(K) и ещё не считая памяти. Для больших K придётся определять found как set или unordered_set (но во второй вставка дороже, емнип)

legolegs ★★★★★ ()
Ответ на: комментарий от legolegs
#include <unordered_set>

using namespace std;

int main()
{
	std::unordered_set<int> s;

	for( int i = 0 ; i < 1000000 ; ++i )
		s.insert( i * 2 );
	
	for( int i = 0 ; i < 1000000 ; ++i )
		s.insert( i * 2 + 1 );
}

real	0m0.220s
user	0m0.156s
sys	0m0.060s
#include <set>

using namespace std;

int main()
{
	std::set<int> s;

	for( int i = 0 ; i < 1000000 ; ++i )
		s.insert( i * 2 );
	
	for( int i = 0 ; i < 1000000 ; ++i )
		s.insert( i * 2 + 1 );
}

real	0m0.544s
user	0m0.500s
sys	0m0.040s
aho_ ()
Ответ на: комментарий от anonymous

привет, alloca

alloca и прочие нестабильности исключительно от краткости (всё-таки тут форум а не git). Выдавать продакшн на вопрос а-ля 'лаба горит' - как то не феньково :)

ТС как раз таки пытается рассуждать

ТС мечется :) Явно нужно решение не для суперскаляров, а лекции и фривольная тех.литература ещё сказывается. Почти нащупал решение - но, блин, лучше посмотреть/спросить соседа по парте :)

и совсем P.S. давая подсказки по лабараторкам, принципиально прячу алгоритмические ошибки; НИКТО из высказавшихся их неувидил на фоне alloca :) rg-400 чё-то чуйкой почуял, но застеснялся что-ли :)

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

MKuznetsov, зачем обнулять mem[K-i] после if (mem[K-i]!=0)? Если на входе [3,5,5] то будет лишь одна пара.

FANATID ()
Ответ на: комментарий от MKuznetsov

и совсем P.S. давая подсказки по лабараторкам, принципиально прячу алгоритмические ошибки; НИКТО из высказавшихся их неувидил на фоне alloca :) rg-400 чё-то чуйкой почуял, но застеснялся что-ли :)

Анонимов не читаешь?

anonymous ()
Ответ на: комментарий от Eddy_Em

А его специально нет. В условиях не сказано, может-ли одно число входить в разные пары. {5, 5, 5, 5} - это сколько пар?

legolegs ★★★★★ ()
Ответ на: комментарий от MKuznetsov

Не говоря о том, что написанное тобой говно требует выделения 16 гигов на стеке (это в лучшем случае), ты как раз и реализовал вариант ОПа, завелосипедив кривой map с константным временем доступа.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.