y***e
发帖数: 32 | 1 如何找到这个pair，有O(log n)的解法吗？
Sorted的队列包含duplicate元素. | h***t
发帖数: 2540 | 2 Yes, binary search, compare 2* arr[mid] with target, then move left or
right, which depends.
【在 y***e 的大作中提到】
: 如何找到这个pair，有O(log n)的解法吗？
: Sorted的队列包含duplicate元素.
| y***e
发帖数: 32 | 3 请问能详细介绍一下。
多谢！
【在 h***t 的大作中提到】
: Yes, binary search, compare 2* arr[mid] with target, then move left or
: right, which depends.
| m********6
发帖数: 58 | 4 How does that work? He is trying to find duplicates. If medium in array a is
10 and medium in array b is 8. How do you move? You know there is no
overlap between right side of array 1(>10) and left side of array b (<8).
You can not infer anything about the other subsets.
Yes, binary search, compare
【在 h***t 的大作中提到】
: Yes, binary search, compare 2* arr[mid] with target, then move left or
: right, which depends.
| m********6
发帖数: 58 | 5 I don't think there is a solution better than O(N) where N is the combined
length of the two arrays. I wasn't able to find a better solution online
either.
How does that work? He is trying to find duplicates. If medium in array a is
10 and medi........
【在 m********6 的大作中提到】
: How does that work? He is trying to find duplicates. If medium in array a is
: 10 and medium in array b is 8. How do you move? You know there is no
: overlap between right side of array 1(>10) and left side of array b (<8).
: You can not infer anything about the other subsets.
:
: Yes, binary search, compare
| y***e
发帖数: 32 | 6 Following hjdut's suggestion, I figured out a O(log n) solution to find a
pair of elements whose sum is equal to the given target.
1. Search for the target in {A[i] + A[i + 1], i = 0, ..., n - 2}
2. If the target is not found in step 1, find i such that A[i - 1] + A[i] <
target < A[i] + A[i + 1].
3. Start from this A[i] + A[i + 1] to explore the given target either
upwards or rightwards in the matrix {m[i,j] = A[i] + A[j]}. Here the
exploring process can be done in binary search way as well, which leads to
the O(log n) solution.
【在 h***t 的大作中提到】
: Yes, binary search, compare 2* arr[mid] with target, then move left or
: right, which depends.
|
|
