Создайте алгоритм для нахождения всех пар целых чисел в массиве, которые суммируются с заданным значением.
Я пробовал эту проблему, используя хеш-таблицу для хранения записей для суммы элементов массива, но это не эффективное решение.
Какой алгоритм я могу использовать для эффективного решения?
Предположим, что требуемая сумма = R
Я не понимаю, почему подход хеш-таблицы неэффективен, по крайней мере, в терминах анализа алгоритмов - в терминах локальности памяти, по общему признанию, это может быть довольно плохо. В любом случае, дважды сканируйте массив...
Первое сканирование - поместить все элементы массива в хэш-таблицу - общее число O (n). Отдельные вставки только амортизируются O (1), но аккуратная вещь о том, как работает амортизационный анализ, означает, что O (n) является абсолютным - не амортизируется.
Второе сканирование - проверка (сумма - ток) в хеш-таблице - O (n) total.
Это превосходит методы сортировки и поиска O (n log n), по крайней мере теоретически.
Затем обратите внимание, что вы можете объединить два сканирования в один. Вы можете определить пару, как только вы столкнетесь со второй из этой пары во время первого сканирования. В псевдокоде...
for i in array.range
hashset.insert (array [i])
diff = sum - array [i]
if hashset.includes (diff)
output diff, array [i]
Если вам нужны позиции предметов, используйте хэш-карту и сохраните позиции позиции в ней. Если вам нужно справиться с дубликатами, вам может потребоваться хранить счета в хэш-карте. Для позиций и дубликатов вам может понадобиться хэш-карта стартовых указателей для связанных списков позиций.
Это делает предположения о реализации хеш-таблицы, но довольно безопасно, учитывая обычные реализации на большинстве современных языков и библиотек.
BTW - объединение сканирования не должно рассматриваться как оптимизация. Накладные расходы итерации должны быть незначительными. Проблемы с локальностью памяти могут сделать один проход немного более эффективным для очень больших массивов, но проблемы с реальной памятью в любом случае будут в хэш-таблице.
IMO - единственная реальная причина объединить сканирование - это потому, что вы хотите, чтобы каждая пара сообщалась один раз - обработка этого в двухскатном подходе была бы немного более сложной.
Если массив отсортирован:
Пусть я = 0, j = конец массива, sum = значение, которое вы ищете, затем выполните:
Если я + j = sum, то вывод (i, j).
Если я + j < sum, затем переместите я в нужное положение.
Если я + j > sum, то переместите j в левую одну позицию.
Сложность времени: O (n). Сложность пространства: O (1).
Если массив не отсортирован, есть несколько способов подойти к этой проблеме:
Сортируйте массив, а затем используйте приведенный выше подход.
HashMap:
Сохраните все элементы в HashMap.
a+b=sum, поэтому b=sum-a. Для каждого элемента a массива найдите b из HashMap.
Поиск HashMap берет амортизацию O (1).
Сложность времени: O (n). Сложность пространства: O (n).
BitMap:
Итерируйте через вход, чтобы создать растровое изображение, где каждый бит соответствует значению элемента. Скажем, что вход {2,5,8}, затем мы переключаем индексы массива битмапа 2, 5 и 8 из двоичного числа 0 в 1. Это принимает O (1) на элемент, таким образом, O (n) в целом.
Пройдите через вход снова. Мы знаем b=sum-a, поэтому для каждого элемента a на входе просмотрите его b, что можно сделать в O(1), так как это растровый индекс. Это также принимает O (n) в целом.
Сложность времени: O (n) + O (n) = O (n). Космическая сложность: растровое пространство = O (n).
Вам даже не нужно хранить все элементы в hashmap, а затем сканировать. Вы можете сканировать во время первой итерации.
void foo(int[] A, int sum) {
HashSet<Integer> set = new HashSet<Integer>();
for (int e : A) {
if (set.contains(sum-e)) {
System.out.println(e + "," + (sum-e));
// deal with the duplicated case
set.remove(sum-e);
} else {
set.add(e);
}
}
}
Как насчет сортировки массива, а затем перехода с обоих концов?
Если вы не против тратить O(M) в пространстве, где M - это сумма, которую вы ищете, вы можете сделать это в O(N + M) времени. Установите sums[i] = 1, когда i <= M за один проход за N, затем проверьте (sums[i] && sums[M-i]) на один проход поверх M/2.
#include <iostream>
using namespace std;
#define MAX 15
int main()
{
int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
const int find_sum = 0;
int max_index = MAX - 1;
int min_index = 0;
while(min_index < max_index)
{
if(array[min_index] + array[max_index-min_index] == find_sum)
{
cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
return 0;
}
if(array[min_index]+array[max_index-min_index] < find_sum)
{
min_index++;
//max_index++;
}
if(array[min_index]+array[max_index-min_index] > find_sum)
{
max_index--;
}
}
cout << "NO MATCH" << endl;
return 0;
}
//-12 & 12 matched
import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
if n[0] + n[1] == targetsum:
print str(n[0]) + " + " + str(n[1])
1 + 4
2 + 3
Вот решение, которое учитывает дубликаты записей. Он написан в javascript и предполагает, что массив отсортирован. Решение работает в O (n) времени и не использует никакой дополнительной памяти, кроме переменной.
var count_pairs = function(_arr,x) {
if(!x) x = 0;
var pairs = 0;
var i = 0;
var k = _arr.length-1;
if((k+1)<2) return pairs;
var halfX = x/2;
while(i<k) {
var curK = _arr[k];
var curI = _arr[i];
var pairsThisLoop = 0;
if(curK+curI==x) {
// if midpoint and equal find combinations
if(curK==curI) {
var comb = 1;
while(--k>=i) pairs+=(comb++);
break;
}
// count pair and k duplicates
pairsThisLoop++;
while(_arr[--k]==curK) pairsThisLoop++;
// add k side pairs to running total for every i side pair found
pairs+=pairsThisLoop;
while(_arr[++i]==curI) pairs+=pairsThisLoop;
} else {
// if we are at a mid point
if(curK==curI) break;
var distK = Math.abs(halfX-curK);
var distI = Math.abs(halfX-curI);
if(distI > distK) while(_arr[++i]==curI);
else while(_arr[--k]==curK);
}
}
return pairs;
}
Итак, это для всех.
Начните с обеих сторон массива и медленно прокладывайте свой путь внутрь, убедившись, что нужно пересчитать дубликаты, если они существуют.
Он учитывает только пары, но может быть переработан на
Наслаждайтесь и не забудьте поднять его, если это лучший ответ!
Решение, которое учитывает дубликаты и использует каждое число только один раз:
void printPairs(int[] numbers, int S) {
// toMap(numbers) converts the numbers array to a map, where
// Key is a number from the original array
// Value is a count of occurrences of this number in the array
Map<Integer, Integer> numbersMap = toMap(numbers);
for (Entry<Integer, Integer> entry : numbersMap.entrySet()) {
if (entry.getValue().equals(0)) {
continue;
}
int number = entry.getKey();
int complement = S - number;
if (numbersMap.containsKey(complement) && numbersMap.get(complement) > 0) {
for (int j = 0; j < min(numbersMap.get(number),
numbersMap.get(complement)); j++) {
if (number.equals(complement) && numbersMap.get(number) < 2) {
break;
}
System.out.println(number, complement);
numbersMap.put(number, numbersMap.get(number) - 1);
numbersMap.put(complement, numbersMap.get(complement) - 1);
}
}
}
}
Решение Hashtable в Ruby (довольно просто понять):
value = 100
pairs = [1,99,5,95]
hash_of_pairs = {}
pairs.map! do |pair|
# Adds to hashtable the pair
hash_of_pairs[pair] = pair
# Finds the value the pair needs
new_pair = hash_of_pairs[value - pair]
# Returns the pair whenever the pair exists, or nil
[new_pair, pair] if !new_pair.nil?
end.compact! # Cleans up the array, removing all nil values
print pairs # [[1,99], [5,95]]
Мы можем использовать С++ STL-карту для решения этой проблемы
void subsetSum(int arr[], int n, int sum)
{
map<int, int>Map;
for(int i=0; i<n; i++)
{
Map[arr[i]]++;
if(Map.count(sum-arr[i]))
{
cout<<arr[i]<<" "<<sum-arr[i]<<"\n";
}
}
}
@Test
public void hasPairWithSum() {
assertFalse(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 3, 9 }, 8));
assertTrue(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 4, 4 }, 8));
assertFalse(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 3, 9 }, 8));
assertTrue(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 4, 4 }, 8));
assertFalse(hasPairWithSum_Unsorted_Linear(new int[] { 9, 1, 3, 2 }, 8));
assertTrue(hasPairWithSum_Unsorted_Linear(new int[] { 4, 2, 1, 4 }, 8));
assertFalse(hasPairWithSum_Unsorted_Quadratic(new int[] { 9, 1, 3, 2 }, 8));
assertTrue(hasPairWithSum_Unsorted_Quadratic(new int[] { 4, 2, 1, 4 }, 8));
}
private boolean hasPairWithSum_Ordered_Logarithmic(int[] data, int sum) {
for (int i = 0; i < data.length; i++) {
int current = data[i];
int complement = sum - current;
int foundIndex = Arrays.binarySearch(data, complement);
if (foundIndex >= 0 && foundIndex != i) {
return true;
}
}
return false;
}
private boolean hasPairWithSum_Ordered_Linear(int[] data, int sum) {
int low = 0;
int high = data.length - 1;
while (low < high) {
int total = data[low] + data[high];
if (total == sum) {
return true;
} else if (total < sum) {
low++;
} else {
high--;
}
}
return false;
}
private boolean hasPairWithSum_Unsorted_Linear(int[] data, int sum) {
Set<Integer> complements = Sets.newHashSet();
for (int current : data) {
if (complements.contains(current)) {
return true;
}
complements.add(sum - current);
}
return false;
}
private boolean hasPairWithSum_Unsorted_Quadratic(int[] data, int sum) {
for (int i = 0; i < data.length; i++) {
int current = data[i];
int complement = sum - current;
for (int j = 0; j < data.length; j++) {
if (data[j] == complement && i != j) {
return true;
}
}
}
return false;
}