Как написать алгоритм, чтобы проверить, соответствует ли сумма любых двух чисел в массиве/списке заданному числу
со сложностью nlogn?
Как написать алгоритм, чтобы проверить, соответствует ли сумма любых двух чисел в массиве/списке заданному числу?
Ответ 1
Я уверен, что есть лучший способ, но вот идея:
- Сортировка массива
- Для каждого элемента e в массиве двоичный поиск дополнения (sum-e)
Обе эти операции: O(n log n).
Ответ 2
Это можно сделать в O(n) с помощью хеш-таблицы. Инициализируйте таблицу всеми числами в массиве, с номером в качестве ключа и частотой в качестве значения. Пройдите через каждое число в массиве и посмотрите, существует ли (sum - number) в таблице. Если это так, у вас есть совпадение. После того, как вы проверили все числа в массиве, вы должны иметь список всех пар, которые суммируются до нужного числа.
array = initial array
table = hash(array)
S = sum
for each n in array
if table[S-n] exists
print "found numbers" n, S-n
Случай, когда n и таблица [S-n] ссылаются на один и тот же номер дважды, могут быть обработаны дополнительной проверкой, но сложность остается O(n).
Ответ 3
Используйте таблицу хеш-таблицы. Вставьте каждое число в свою хеш-таблицу вместе со своим индексом. Тогда пусть S будет вашей желаемой суммой. Для каждого номера array[i] в вашем начальном массиве см., Существует ли S - array[i] в вашей хэш-таблице с индексом, отличным от i.
Средний случай O(n), худший случай O(n^2), поэтому используйте решение для двоичного поиска, если вы боитесь худшего случая.
Ответ 4
Скажем, что мы хотим найти два числа в массиве A, которые при объединении равны N.
- Сортировка массива.
- Найдите наибольшее число в массиве, которое меньше N/2. Установите индекс этого числа как ниже.
- Инициализировать верхний, чтобы быть ниже + 1.
- Установить сумму = A [нижняя] + A [верхняя].
- Если сумма == N, выполнена.
- Если сумма < N, верхний верхний.
- Если суммa > N, уменьшитесь ниже.
- Если либо нижний, либо верхний находится вне массива, выполняется без каких-либо совпадений.
- Вернитесь к 4.
Сорт может быть выполнен в O (n log n). Поиск выполняется в линейном времени.
Ответ 5
Это на Java: это даже удаляет возможные дубликаты.. Время выполнения - O(n^2)
private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;
private static void algorithm()
{
Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
for (int i=0; i<intArray.length; i++)
{
intMap.put(i, intArray[i]);
if(intMap.containsValue(sum - intArray[i]))
System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));
}
System.out.println(intMap);
}
Ответ 6
def sum_in(numbers, sum_):
"""whether any two numbers from `numbers` form `sum_`."""
a = set(numbers) # O(n)
return any((sum_ - n) in a for n in a) # O(n)
Пример:
>>> sum_in([200, -10, -100], 100)
True
Ответ 7
Здесь попытка в C. Это не помечено домашнее задание.
// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
int i = 0, k = size - 1;
int curSum;
while(i < k)
{
curSum = array[i] + array[k];
if(curSum == sum)
{
printf("Found match at indices %d, %d\n", i, k);
i++;k--;
}
else if(curSum < sum)
{
i++;
}
else
{
k--;
}
}
}
Вот несколько тестовых результатов с использованием int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };
Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..
Поиск является линейным, поэтому O (n). Сорт, который происходит за кулисами, будет O (n * logn), если вы используете один из хороших сортов.
Из-за математики за Big-O меньший член в аддитивных терминах эффективно выпадет из ваших вычислений, и вы закончите с O (n logn).
Ответ 8
Это O (n)
public static bool doesTargetExistsInList(int Target, int[] inputArray)
{
if (inputArray != null && inputArray.Length > 0 )
{
Hashtable inputHashTable = new Hashtable();
// This hash table will have all the items in the input array and how many times they appeard
Hashtable duplicateItems = new Hashtable();
foreach (int i in inputArray)
{
if (!inputHashTable.ContainsKey(i))
{
inputHashTable.Add(i, Target - i);
duplicateItems.Add(i, 1);
}
else
{
duplicateItems[i] = (int)duplicateItems[i] + 1;
}
}
foreach (DictionaryEntry de in inputHashTable)
{
if ((int)de.Key == (int)de.Value)
{
if ((int)duplicateItems[de.Key] > 1)
return true;
}
else if (inputHashTable.ContainsKey(de.Value))
{
return true;
}
}
}
return false;
}
Ответ 9
Вот алгоритм, который работает в O (n), если массив уже отсортирован или O (n log n), если он еще не отсортирован. Здесь вы найдете ответы на множество других ответов. Код находится на Java, но здесь есть псевдокод, также полученный из множества существующих ответов, но оптимизированный для дубликатов вообще
- Счастливчик, если первый и последний элементы равны цели
- Создать карту с текущим значением и его вхождениями
- Создайте посещенный набор, который содержит элементы, которые мы уже видели, это оптимизирует для дубликатов, которые говорят с вводом (1,1,1,1,1,1,2) и целевого 4, мы только вычисляем для 0 и последний элемент, а не все 1 в массиве.
-
Используйте эти переменные для вычисления существования цели в массиве; установите currentValue в массив [i]; set newTarget для таргетинга - currentValue; set expectedCount до 2, если currentValue равно newTarget или 1 в противном случае
И верните true, только если а. мы никогда не видели это целое число до И б. у нас есть некоторое значение для newTarget на карте, которую мы создали с. и счетчик для newTarget равен или больше, чем ожидаемый счетчик
ИНАЧЕ повторите шаг 4 до тех пор, пока мы не достигнем конца массива и не вернем false OTHERWISE;
Как я уже упоминал, наилучшее использование для посещенного магазина - это когда у нас есть дубликаты, это никогда не поможет, если ни один из элементов не дублирует.
Код Java в https://gist.github.com/eded5dbcee737390acb4
Ответ 10
Зависит Если вы хотите получить только одну сумму O (N) или O (N log N) или все суммы O (N ^ 2) или O (N ^ 2 log N). В последнем случае лучше использовать FFT >
Ответ 11
Шаг 1: Сортировка массива в O (n logn)
Шаг 2: Найдите два индекса
0 <= я < j <= n в [0..n], что a [i] + a [j] == k, где k задан ключ.
int i=0,j=n;
while(i<j) {
int sum = a[i]+a[j];
if(sum == k)
print(i,j)
else if (sum < k)
i++;
else if (sum > k)
j--;
}
Ответ 12
public void sumOfTwoQualToTargetSum()
{
List<int> list= new List<int>();
list.Add(1);
list.Add(3);
list.Add(5);
list.Add(7);
list.Add(9);
int targetsum = 12;
int[] arr = list.ToArray();
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
if ((i != j) && ((arr[i] + arr[j]) == targetsum))
{
Console.Write("i =" + i);
Console.WriteLine("j =" + j);
}
}
}
}
Ответ 13
- Решил вопрос в Swift 4.0
- Решено тремя различными способами (с 2-мя разными типами возврата → Булевыми и Индексами)
A) TimeComplexity = > 0 (n Log n) SpaceComplexity = > 0 (n).
B) TimeComplexity = > 0 (n ^ 2) SpaceComplexity = > 0 (1).
C) TimeComplexity = > 0 (n) SpaceComplexity = > 0 (n)
-
Выберите решение A, B или C в зависимости от TradeOff.
//***********************Solution A*********************// //This solution returns TRUE if any such two pairs exist in the array func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //Helper Function if end < start { return -1 } else { let midIndex = (start + end) / 2 if list[midIndex] > key { return binarySearch(list: list, key: key, start: start, end: midIndex - 1) } else if list[midIndex] < key { return binarySearch(list: list, key: key, start: midIndex + 1, end: end) } else { return midIndex } } } func twoPairSum(sum : Int, inputArray: [Int]) -> Bool { //Do this only if array isn't Sorted! let sortedArray = inputArray.sorted() for (currentIndex, value) in sortedArray.enumerated() { if let indexReturned = binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) { if indexReturned != -1 && (indexReturned != currentIndex) { return true } } } return false } //***********************Solution B*********************// //This solution returns the indexes of the two pair elements if any such two pairs exists in the array func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] { for currentIndex in 0..<nums.count { for nextIndex in currentIndex+1..<nums.count { if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) { return [currentIndex, nextIndex] } } } return [] } func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//Helper Function return (firstElement + secondElement) == target } //*******************Solution C*********************// //This solution returns the indexes of the two pair elements if any such two pairs exists in the array func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] { var dict = [Int: Int]() for (index, value) in nums.enumerated() { dict[value] = index } for (index, value) in nums.enumerated() { let otherIndex = dict[(target - value)] if otherIndex != nil && otherIndex != index { return [index, otherIndex!] } } return [] }
Ответ 14
В этом вопросе отсутствуют некоторые подробности. Как то, что является возвращаемым значением, ограничение на входе.
Я видел несколько вопросов, связанных с этим, которые могут быть этим вопросом с дополнительным требованием, to return the actual elements that result in the input
Вот моя версия решения, это должно быть O(n).
import java.util.*;
public class IntegerSum {
private static final int[] NUMBERS = {1,2,3,4,5,6,7,8,9,10};
public static void main(String[] args) {
int[] result = IntegerSum.isSumExist(7);
System.out.println(Arrays.toString(result));
}
/**
* n = x + y
* 7 = 1 + 6
* 7 - 1 = 6
* 7 - 6 = 1
* The subtraction of one element in the array should result into the value of the other element if it exist;
*/
public static int[] isSumExist(int n) {
// validate the input, based on the question
// This to return the values that actually result in the sum. which is even more tricky
int[] output = new int[2];
Map resultsMap = new HashMap<Integer, Integer>();
// O(n)
for (int number : NUMBERS) {
if ( number > n )
throw new IllegalStateException("The number is not in the array.");
if ( resultsMap.containsKey(number) ) {
output[0] = number;
output[1] = (Integer) resultsMap.get(number);
return output;
}
resultsMap.put(n - number, number);
}
throw new IllegalStateException("The number is not in the array.");
}
}