Я должен создать алгоритм O(n log(n)), который проверяет, является ли сумма 2 чисел в int [] == заданным числом.
например. Учитывая [1,4,7,2,3,4], будет сумма 8 (1 + 7), но не 20
В данном ответе предложены двоичная сортировка или сортировка слиянием, но они просто дали алгоритм сортировки слиянием без логической обработки этого конкретного требования. Тогда другой ответ был:
Предположим, что x это сумма, которую мы хотим проверить, z это набор элементов в
этот массив: следующий алгоритм решает проблему:
- Сортировка элементов в S.
- Формируем множество S ’= {z: z = x - y для некоторого y ∈ S}.
- Сортировать элементы по S '.
- Если какое-либо значение в S появляется более одного раза, удалите все, кроме одного экземпляра. Сделайте то же самое для S ’.
- Объединить два отсортированных набора S и S ’.
- Существует два элемента в S, сумма которых равна x тогда и только тогда, когда одно и то же значение появляется в последовательных позициях в объединенном выводе.
Чтобы обосновать претензию на шаге 4, сначала обратите внимание, что если есть какое-либо значение
появляется дважды в объединенном выводе, он должен появляться последовательно
позиции. Таким образом, мы можем переформулировать условие на шаге 5, если оно существует
два элемента в S, сумма которых в точности равна x тогда и только тогда, когда одно и то же значение
появляется дважды в объединенном выводе. Предположим, что появляется некоторое значение w
дважды. Затем w появился один раз в S и один раз в S ’. Потому что ш появился в
S ’, существует такой y ∈ S, что w = x - y или x = w + y. С ж
∈ S, элементы w и y находятся в S и суммируются с x.
Наоборот, предположим, что существуют такие значения w, y ∈ S, что w + y =
Икс. Тогда, поскольку x - y = w, значение w появляется в S ’. Таким образом, w находится в
и S, и S ’, и поэтому он будет отображаться дважды в объединенном выводе.
Шаги 1 и 3 требуют O (n log n) шагов. Шаги 2, 4, 5 и 6 требуют
O (n) шагов. Таким образом, общее время работы O (n log n).
Но я не совсем понимаю, что они имели в виду. На шаге 2, что такое х и у?
Но я создал свой собственный ниже, интересно, если это O(n log(n))?
class FindSum {
public static void main(String[] args) {
int[] arr = {6,1,2,3,7,12,10,10};
int targetSum = 20;
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
int end = arr.length - 1;
if (FindSum.binarySearchSum(arr, targetSum, 0, end, 0, end)) {
System.out.println("Found!");
} else {
System.out.println("Not Found :(");
}
}
public static boolean binarySearchSum(int[] arr, int targetSum,
int from1, int end1,
int from2, int end2) {
// idea is to use 2 "pointers" (simulating 2 arrays) to (binary) search
// for target sum
int curr1 = from1 + (end1-from1)/2;
int curr2 = from2 + (end2-from2)/2;
System.out.print(String.format("Looking between %d to %d, %d to %d: %d, %d", from1, end1, from2, end2, curr1, curr2));
int currSum = arr[curr1] + arr[curr2];
System.out.println(". Sum = " + currSum);
if (currSum == targetSum) {
// base case
return true;
} else if (currSum > targetSum) {
// currSum more than targetSum
if (from2 != end2) {
// search in lower half of 2nd "array"
return FindSum.binarySearchSum(arr, targetSum, from1, end1, from2, curr2 - 1);
} else if (from1 != end2) {
// search in lower half of 1st "array" (resetting the start2, end2 args)
return FindSum.binarySearchSum(arr, targetSum, from1, curr1 - 1, 0, arr.length - 1);
} else {
// can't find
return false;
}
} else {
// currSum < targetSum
if (from2 != end2) {
// search in upper half of 2nd "array"
return FindSum.binarySearchSum(arr, targetSum, from1, end1, curr2 + 1, end2);
} else if (from1 != end2) {
// search in upper half of 1st "array" (resetting the start2, end2 args)
return FindSum.binarySearchSum(arr, targetSum, curr1 + 1, end1, 0, arr.length - 1);
} else {
// can't find
return false;
}
}
}
}