Псевдокод для поиска по массиву

Вопрос:

«Напишите алгоритм, который при заданном массиве A и целочисленном значении k возвращает значение true, если в A есть два разных целых числа, сумма которых равна k, и возвращает false в противном случае».

Мой псевдокод:

Вход: массив A размера n со значением k

Вывод: истина, если сумма двух разных целых чисел в А равна k, в противном случае ложь.

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
    for (j=i+1, j<n, j++)
        if (A[i]+A[j]=k)
            return true
return false

Я правильно написал этот алгоритм? Есть ли ошибки, которых я просто не вижу?


arrays algorithm pseudocode
person Community    schedule 25.09.2012    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Если два разных целых числа означают A[i], A[j], где i != j, а не A[i] != A[j], ваш псевдокод правильный.

person Marcus    schedule 25.09.2012
comment
Извините за двусмысленность. Каждая позиция в массиве содержит уникальное целое число. Например, приведенный в качестве примера массив был [4|7|3|9|2|1|5]. Мы предназначены для сравнения/суммирования содержимого массива, а не позиций. - person ; 25.09.2012
comment
Здорово! Спасибо вам за помощь. - person ; 25.09.2012
comment
@ user41419 Маркус правильно упомянул сравнение позиций. Однако в вашем алгоритме это сравнение всегда будет истинным, поэтому в нем нет необходимости. - person phant0m; 25.09.2012

arrow_upward
2
arrow_downward

У меня есть два решения проблемы

Первое решение

1.Создать пустой хэш
2.Отметить все числа в массиве в хеше

 for each i (Array A){
        hash[i] = 1;
    }

3.Просто запустите цикл O(n)

for each i (Array A)
    if(  hash[ k - i ] ) 
        print "solution i and k-i"

Это даст вам O(n) сложности

Второе решение

1. Отсортировать массив
2. Запустить цикл O(n) по отсортированному массиву.

for each i (Array A)
    binary_search( Array, k - i); [log n operation]

Это даст вам O(n logn) сложности.

person Atanu    schedule 25.09.2012
comment
Я думаю, что второе решение более удобно. - person Samiron; 25.09.2012
comment
чтобы сохранить осадок памяти, да. второй метод не требует дополнительных мест в памяти. - person Atanu; 25.09.2012

arrow_upward
0
arrow_downward

Это похоже на случай проблемы с рюкзаком.

В вашем случае (только два числа) может быть лучше отсортировать массив, чтобы уменьшить количество сравнений (A[i]+A[j]=k).

Например:

you have sorted array [1 3 5 8 10 12 14 20 50 60 100]
sum of two numbers must be equal to 30

Тогда вы можете написать

 while(a[i] <= 30) {
   while(a[i] + a[j] <= 30) {
    // ...
    i++;
    j++;
   } 
 }
person demas    schedule 25.09.2012