O(n log(n)) 算法，检查 int[] 中的 2 个数字之和是否 = 给定数字
我应该创建一个 O(n log(n)) 算法来检查 int[] == 给定数字中 2 个数字的总和。
例如。给定[1,4,7,2,3,4]，总和为8（1+7），但不是20
给出的答案建议二元排序或归并排序，但他们只是给出了归并排序算法，没有进行逻辑处理这个特殊的要求。然后另一个答案是：
假设 x 是我们要检查的总和，z 是中的元素集合 这个数组：以下算法解决了这个问题：
- 对 S 中的元素进行排序。
- 对于某些 y ∈ S，形成集合 S' = {z : z = x − y}。
- 对 S' 中的元素进行排序。
- 如果 S 中的任何值出现多次，则删除除一个实例之外的所有实例。对 S' 执行同样的操作。
- 合并两个排序集 S 和 S'。
- 当且仅当合并输出中的连续位置出现相同值时，S 中存在两个元素，其总和恰好为 x。
为了证明第 4 步中的主张合理，首先观察是否有任何值 在合并输出中出现两次，它必须连续出现 职位。因此，我们可以重申第 5 步中的条件，因为存在 S 中的两个元素，其总和恰好为 x 当且仅当值相同 在合并输出中出现两次。假设出现某个值 w 两次。然后w在S中出现一次，在S'中出现一次。因为w出现在 S'，存在一些 y ∈ S 使得 w = x − y，或 x = w + y。自从w ε S，元素w和y在S中，和为x。
相反，假设有值 w, y ∈ S 使得 w + y = x。然后，由于 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 中，x 和 y 是什么？
但是我下面自己创建的，我想知道它是否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;
}
}
}
}
I am supposed to create a O(n log(n)) algorithm that checks if sum of 2 numbers in a int[] == given number.
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:
Suppose x is the sum we want to check, z is the set of elements in
this array: The following algorithm solves the problem:
- 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.
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.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.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).
But I don't really what they meant. In step 2, what are x and y?
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;
}
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
与 @user384706 类似，但是您可以在
O(n)中完成此操作。他们的说法如下：
S=[1,4,7,2,3,4]
将这些添加到 HashSet 中，理想情况下是 TIntHashSet（但时间复杂度相同）
打印
Similar to @user384706, however you can do this with in
O(n).What they say is the following:
S=[1,4,7,2,3,4]
Add these to a HashSet, ideally TIntHashSet (but the time complexity is the same)
prints
他们的说法如下：
S=[1,4,7,2,3,4]使用归并排序对 S 进行排序，得到
Ss=[1,2,3,4,7]。成本是O(nlogn)- 只需检查 wiki 即可。那么你就有
x=8因此，通过用
S中的元素减去x就可以形成S'=[7,6,5,4,1]。在
O(nlogn)中使用归并排序对S'进行排序删除重复项需要
O(n)。然后合并
Ss和S'。您在
O(n)中检查连续位置中的重复项。总计为：
O(nlogn)+O(nlogn)+O(n)+O(n)+O(n) = O(nlogn)What they say is the following:
S=[1,4,7,2,3,4]Sort S using mergesort you get
Ss=[1,2,3,4,7]. Cost isO(nlogn)- just check wiki for this.Then you have
x=8So you form
S'=[7,6,5,4,1]by subtractingxwith the elements inS.Sort
S'using mergesort inO(nlogn)Remove duplicates requires
O(n).Then you merge the
SsandS'.You check for duplicates in consecutive positions in
O(n).Total is:
O(nlogn)+O(nlogn)+O(n)+O(n)+O(n) = O(nlogn)O(n) 解决方案怎么样？
从您的问题中尚不清楚您是否应该使用您所描述的“另一个答案”[原文如此]，或者您是否可以提出自己的解决方案。
您应该问的第一件事是“有什么要求？”因为有限制。您将收到的最大整数是多少？两百万？一千万？这些整数的范围是多少？在你的问题中，它们似乎总是大于零。这些整数的最大值是多少？您可以使用多少内存？
因为总是需要权衡。
例如，这是一个针对您的问题的非优化（见下文）O(n) 解决方案（我在您的输入中添加了“8”）：
它是非优化的，因为很容易编写 O(n) >O(n) 使用“仅”1 GB 内存来处理从 0 到 2**31 的整数（您可以使用位而不是像我在这里那样使用整数来表示 S 和 S'）。
当然，人们可能会认为“但是 1GB 是很大的内存”：但这一切都取决于要求。我上面的解决方案（或其优化版本）是O(n)，并且可以立即解决由一亿个整数组成的输入，而任何其他解决方案都会失败（因为你'由于 Java 对象的开销，d 有 OutOfMemory 错误。
首先要问的是“有什么要求？”。您需要有关输入的更多信息，因为这始终是一种权衡。
What about an O(n) solution?
It's not clear from your question if you're supposed to use what you described as "another answer" [sic] or if you can come up with your own solution.
The first thing you should ask is "what are the requirements?" Because there are limitations. What's the maximum number of integers you'll receive? Two millions? Ten millions? What's the range of these integers? In your question they always seem greater than zero. What's the maximum value these integers can have? How much memory can you use?
Because there are always tradeoffs.
For example here's a non-optimized (see below) O(n) solution to your problem (I added an '8' to your input):
It's non optimized in that it's easy to write an O(n) working for integers from 0 to 2**31 using "only" 1 GB of memory (where you'd represent your S and your S' using bits instead of ints like I did here).
Sure, one may think "but 1GB is a lot of memory": but it all depends on the requirements. My solution above (or an optimized version of it) is O(n) and can solve an input made of, say, 100 millions integers in no time, where any other solution would fail (because you'd have OutOfMemory errors due to the overhead of Java objects).
The first thing to ask is "What are the requirements?". You need more information about the input because it's always a tradeoff.
你的算法是 O(n log n)。每次您将第一个数组大小除以二或对第二个数组进行二分搜索。这是 O((log n) ^2) 最坏情况（即 S = {1,2...,n} 且 x = 0），因此它被排序吸收。
无论如何，您可以通过以下方式在 O(n log n) 中更轻松地做到这一点：
编辑：
回答你的第一个问题。 x 是您要查找的总和，y 是输入集的元素。因此，如果 S= {y_1, y_2, y_3,..., y_n} 则 S' = {x - y_1, x - y_2, x - y_3, ...x - y_n}
Your algorithm is O(n log n). Each time you either divide 1st array size by two or do a binary search on the second one. This is O((log n) ^2) worst case (ie. S = {1,2...,n} and x = 0) and hence it's absorbed by sorting.
Anyway you can do it a bit easier in O(n log n) by:
edit:
In response to your first question. x is the sum you're looking for and y are the elements of the input set. So if S= {y_1, y_2, y_3,..., y_n} then S' = {x - y_1, x - y_2, x - y_3, ...x - y_n}
它的工作原理如下：
}
It works as following :
}