P*****o
发帖数: 294 | 1 4组整数数组,前三组每组取出一个数相加,如果sum在第四个数组里面返回结果
这个怎么做啊 | P*****o
发帖数: 294 | | c***2
发帖数: 838 | 3 For unsorted arrays:
grab 3 numbers: n^3
search sum from 4th: n
O(n^4) | P*****o
发帖数: 294 | 4
谢谢啊,刚电面的goog估计悲剧了
【在 c***2 的大作中提到】
: For unsorted arrays:
: grab 3 numbers: n^3
: search sum from 4th: n
: O(n^4)
| d**e
发帖数: 6098 | 5 sort all 4 arrays into a big one
这个怎么做？怎么保证取的三数来自不同的数组？
【在 c***2 的大作中提到】
: For unsorted arrays:
: grab 3 numbers: n^3
: search sum from 4th: n
: O(n^4)
| j****a
发帖数: 55 | 6 写了一下，不知道对不对...
int findExistingSum(int* a1, int* a2, int* a3, int* a4, int size) {
a1 = sort(a1);
a2 = sort(a2);
a3 = sort(a3);
a4 = sort(a4);
for (int i4 = 0; i4 < size; i4++) {
// binarySearchSmaller returns the index of the element that is
smaller or equal to the second parameter.
int bound3 = binarySearchSmaller(a3, a4[i4], size);
for (int i3 = 0; i3 <= bound3; i3++) {
int bound2 = binarySearchSmaller(a2, a4[i4] - a3[i3], size);
for (int i2 = 0; i2 <= bound2; i2++) {
int bound1 = binarySearchSmaller(a2, a4[i4] - a3[i3] - a2[i2
], size);
if (a4[i4] - a3[i3] - a2[i2] - a1[bound1] == 0) {
return a4[i4];
}
}
}
}
}
int binarySearchSmaller(int* a, int value, size) {
int index = size/2;
while (true) {
if (index/2 == 0) {
if (a[index] == value) {
return index;
} else {
return index - 1;
}
}
if (a[index] == value) {
return index;
} else if (a[index] < value) {
index += index/2;
} else if (a[index] > value) {
index -= index/2;
}
}
} | x***y
发帖数: 633 | 7 To make sure taking one number out of each first 3 arrays, we can do it like
this:
get all the possible sum of one number in the first array and one number in
the second array(O(n^2), assume each array is O(n)size. We can also store
the information about which two number makes the sum)
get all the possible difference between one number in the 4th array and one
number in the 3rd array. (Also O(n^2), and store additional information.)
Use hash table to verify whether one number in the sum result is also in the
difference result. Also, O(n^2).
Totally , it's O(n^2).
【在 P*****o 的大作中提到】
: 4组整数数组,前三组每组取出一个数相加,如果sum在第四个数组里面返回结果
: 这个怎么做啊
| P*****o
发帖数: 294 | 8 也有想到这种,不过比较两个长度是O(n^2)的数组,我当时咋一下以为是n^4,后来仔细一
想如果先排序
不就好了吗
like
in
store
one
information.)
the
【在 x***y 的大作中提到】
: To make sure taking one number out of each first 3 arrays, we can do it like
: this:
: get all the possible sum of one number in the first array and one number in
: the second array(O(n^2), assume each array is O(n)size. We can also store
: the information about which two number makes the sum)
: get all the possible difference between one number in the 4th array and one
: number in the 3rd array. (Also O(n^2), and store additional information.)
: Use hash table to verify whether one number in the sum result is also in the
: difference result. Also, O(n^2).
: Totally , it's O(n^2).
|
|
