问题描述
我应该创建一个 O（n log（n））算法，该算法检查int [] ==给定数字中是否有2个数字的总和。
I am supposed to create a O(n log(n)) algorithm that checks if sum of 2 numbers in a int[] == given number.
例如。鉴于[1,4,7,2,3,4]将有8（1 + 7）但不是20
eg. Given [1,4,7,2,3,4] there will be a sum 8 (1+7) but not 20
给出的答案建议二进制排序或合并排序，但他们只给出了合并排序算法，而没有逻辑处理这个特殊要求。然后另一个答案是：
The given answer suggested Binary Sort or Merge Sort, but they just gave the merge sort algorithm without the logic processing this particular requirement. Then another answer was:
- 对S中的元素进行排序。
- 形成集合S'= {z：z = x - y表示y∈S}。
- 对S'中的元素进行排序。
- 如果有任何值在S中出现不止一次，删除除一个实例以外的所有实例。对S'执行相同操作。
- 合并两个有序集合S和S'。
- S中存在两个元素，其总和正好为x当且仅当相同的值出现在合并输出的连续位置时。
- Sort the elements in S.
- Form the set S’ = {z : z = x − y for some y ∈ S}.
- Sort the elements in S'.
- If any value in S appears more than once, remove all but one instance. Do the same for S’.
- Merge the two sorted sets S and S’.
- There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.
为了证明步骤4中的声明，首先要注意如果任何值
在合并输出中出现两次，则它必须出现在连续的
位置。因此，我们可以重复步骤5中的条件，因为在S中存在
两个元素，当且仅当相同的值
在合并输出中出现两次时，其总和才是x。假设某个值w出现
两次。然后w在S中出现一次，在S'出现一次。因为w出现在
S'中，所以存在一些y∈S，使得w = x-y，或x = w + y。由于w $ b $b∈S，元素w和y在S中并且总和为x。
To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in S whose sum is exactly x if and only if the same value appears twice in the merged output. Suppose that some value w appears twice. Then w appeared once in S and once in S’. Because w appeared in S’, there exists some y ∈ S such that w = x − y, or x = w + y. Since w ∈ S, the elements w and y are in S and sum to x.
相反，假设存在值w，y∈S等那个w + y =
x。然后，由于x-y = w，值w出现在S'中。因此，w在S和S'中都是
，因此它在合并输出中会出现两次。
Conversely, suppose that there are values w, y ∈ S such that w + y = x. Then, since x − y = w, the value w appears in S’. Thus, w is in both S and S’, and so it will appear twice in the merged output.
步骤1和3需要O（n log） n）步骤。步骤2,4,5和6需要
O（n）步。因此整体运行时间为O（n log n）。
Steps 1 and 3 require O(n log n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n log n).
但我真的不是他们的意思。在第2步中，x和y是什么？
But I don't really what they meant. In step 2, what are x and y?
但是我自己在下面创建，我想知道它的 O（n log（n）） ？
But I created by own below, I wonder if its 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;
}
}
}
}
推荐答案
与@ user384706类似，但您可以在 O（n）中执行此操作。
Similar to @user384706, however you can do this with in O(n).
他们所说的如下：
S = [1,4,7,2,3,4]
What they say is the following:S=[1,4,7,2,3,4]
添加这些是HashSet，理想情况是TIntHashSet（但时间复杂度相同）
Add these to a HashSet, ideally TIntHashSet (but the time complexity is the same)
int total = 9;
Integer[] S = {1, 4, 7, 2, 3, 4, 6};
Set<Integer> set = new HashSet<Integer>(Arrays.asList(S));
for (int i : set)
if (set.contains(total - i))
System.out.println(i + " + " + (total - i) + " = " + total);
打印
2 + 7 = 9
3 + 6 = 9
6 + 3 = 9
7 + 2 = 9
这篇关于O（n log（n））算法，检查int []中给定数字的2个数之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！