f*********i
发帖数: 197 | 1 Given two arrays A and B in ascending order with size m and n, respectively,
question:
find the Kth largest sum(a+b) where a in A and b in B, 1 |
g***s
发帖数: 3811 | 2 It is a Young Tableau.
easy to find a way using max-heap in O(klogk).
respectively,
【在 f*********i 的大作中提到】
: Given two arrays A and B in ascending order with size m and n, respectively,
: question:
: find the Kth largest sum(a+b) where a in A and b in B, 1
|
g*****k
发帖数: 623 | 3 I dont think it is a Young Tableau where column is sorted also.
and this questions seems have O(k) solution.
【在 g***s 的大作中提到】
: It is a Young Tableau.
: easy to find a way using max-heap in O(klogk).
:
: respectively,
|
g**e
发帖数: 6127 | 4 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
【在 g*****k 的大作中提到】
: I dont think it is a Young Tableau where column is sorted also.
: and this questions seems have O(k) solution.
|
g*****k
发帖数: 623 | 5 不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
This should be similiar to the above casee
}
}
【在 g**e 的大作中提到】
: 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
: 道怎么用。
: 这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
|
g***s
发帖数: 3811 | 6 I also think there is O(k) solution. since O(klogk) only uses the Young-
Tabeleau but the maxtrix of sum(a,b) is stonger than a Young-Tableleau.
Another way for O(klogk) (not using max-heap):
1. pickup k elements from first line:
2. pickup k/2 elements from 2nd line:
...
j. pickup k/j elements from jth line
...
k. pickup 1 elements from kth line
total number of elements is sum(1/j) < klogk. then find the kth, is
O(klogk).
It is still only uses the feature of Young-Tableleau, not sum-feature.
【在 g**e 的大作中提到】
: 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
: 道怎么用。
: 这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
|
g***s
发帖数: 3811 | 7 "题目没说每行和每列之间是个定值"
the delta values of each line are same.
a1+b1 a1+b2 a1+b3.... a1+bn
a2+b1 a2+b2 a2+b3.... a2+bn
delta values are {b_i - b_i-1}
【在 g*****k 的大作中提到】
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
|
g*****k
发帖数: 623 | 8 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
This should be similiar to the above casee
}
}
【在 g*****k 的大作中提到】
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
|
g*****k
发帖数: 623 | 9 这里取a+b,a是来自A[]数组， b来自B[]数组。
没有完全看懂。
但是
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1)
array1.second = array2.first +1;
else
array 1: 0 3 ....
array 2: 2 3 4....
array1[0] + array1[1] < array1[0] + array2[2] < array2[0] + array2[1]
array2[0] + array1[1] = array2[0] + array2[1]
看不出来array1[0] + array2[2] 怎么handle的. |
g*****k
发帖数: 623 | 10 完整code
vector > findK(vector &v1, vector &v2, int k){
if (v1.empty() || v2.empty()) return vector >();
vector > res;
res.push_back(make_pair(0, 0));
pair a1(0, 1);
pair a2(0, 1);
for (int i = 1; i
if (v1[a1.first] + v2[a1.second] <= v2[a2.first] + v1[a2.second]) {
res.push_back(a1);
if (a1.second == v2.size() - 1){
a1.second = a2.first + 1;
a1.first += 1;
}
else {
a1.second += 1;
}
}
else {
res.push_back(make_pair(a2.second, a2.first));
if (a2.second == v1.size() - 1) {
a2.second = a1.first + 1;
a2.first += 1;
}
else {
a2.second += 1;
}
}
}
return res;
}
void print(vector > v)
{
for (int i = 0; i < v.size(); ++i) {
cout << "A[" << v[i].first << "] + B[" << v[i].second << "]"
<< endl;
}
}
【在 g*****k 的大作中提到】
: 这里取a+b,a是来自A[]数组， b来自B[]数组。
:
: 没有完全看懂。
: 但是
: if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
: res[i] = A[array1.first]+B[array1.second;
: if (array1.second = m - 1)
: array1.second = array2.first +1;
: else
: array 1: 0 3 ....
|
|
|
g*****k
发帖数: 623 | 11 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
这完全没有必要
【在 g***s 的大作中提到】
: "题目没说每行和每列之间是个定值"
: the delta values of each line are same.
: a1+b1 a1+b2 a1+b3.... a1+bn
: a2+b1 a2+b2 a2+b3.... a2+bn
: delta values are {b_i - b_i-1}
|
g***s
发帖数: 3811 | 12 not correct.
{
【在 g*****k 的大作中提到】
: 完整code
: vector > findK(vector &v1, vector &v2, int k){
: if (v1.empty() || v2.empty()) return vector >();
: vector > res;
: res.push_back(make_pair(0, 0));
: pair a1(0, 1);
: pair a2(0, 1);
: for (int i = 1; i: if (v1[a1.first] + v2[a1.second] <= v2[a2.first] + v1[a2.second]) {
: res.push_back(a1);
|
g***s
发帖数: 3811 | 13 just use it to explain. not need to build matrix.
m(i,j) = a(i) + b(j). when we need it, just get it.
【在 g*****k 的大作中提到】
: 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
: 这完全没有必要
|
g**e
发帖数: 6127 | 14 this is wrong... try more samples, hehe
度。
不知
【在 g*****k 的大作中提到】
: 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
:
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
|
g*****k
发帖数: 623 | 15 麻烦给各例子，好debug阿
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
|
g*****k
发帖数: 623 | 16 麻烦指出出错的地方哦
【在 g***s 的大作中提到】
: not correct.
:
: {
|
s*****y
发帖数: 897 | 17 同求，run了好几个例子，都是对的。
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
|
g***s
发帖数: 3811 | 18 很多元素都没用被检测而直接跳过了
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
|
g*****k
发帖数: 623 | 19 没问题啊，哪里错了？
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
|
g*****k
发帖数: 623 | 20 A[0]+A[1]不属于解，两个数必须分别属于两个数组。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
|
|
|
g*****k
发帖数: 623 | 21 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
|
g***s
发帖数: 3811 | 22 在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
|
g*****k
发帖数: 623 | 23 不明白，你说的再加一行指什么？
题目不是说给定两个数组找出第K大的a+b吗？
我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
这两个数组都是什么？
1 3 7
4 6 10
5 7 11
这个是对应的哪两个数组啊？
【在 g***s 的大作中提到】
: 在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
: 1 3 7
: 4 6 10
: 5 7 11
: 那么出来的就是1 3 4 6
|
d*******l
发帖数: 338 | 24 你这个想法倒是有可能是on the right track，不过目前的代码有问题吧，你试试A和B
都是1,2,3,4,5五个数，求第6个数就有问题啊
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
|
g***s
发帖数: 3811 | 25 a={1,4,7}
b={0,2,6}
k=4
your codes will output
1,3,4,7
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
|
d*******l
发帖数: 338 | 26 我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
|
g***s
发帖数: 3811 | 27 这个是错的还是很明白的。不是单纯重复的问题
1 3 8
4 6 11
7 9 14
看样式矩阵，它每次都是在两个候选里面找小的。如果是v1,就往右走(不care下面的元
素）；如果是
v2，就往下走（不care右边的元素）。这样才导致不会增加候选，否则，每次应该增加
两个（最多）候
选，k步最多是2k个元素。那么在候选里面挑最大（小）的元素，就不是一个O(1)了，
而需要heap来维
持，这就是为什么klogk
感觉O(k)的方法应该不需要把前k个元素一个一个列出来。
【在 d*******l 的大作中提到】
: 我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
: candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
: 也不敢说一定就不行，要证明是错的也并不必证明是对的容易
|
g**e
发帖数: 6127 | 28 以前的讨论
http://mitbbs.com/article_t/JobHunting/31611383.html
stackoverflow上的人给出的O(sqrt(k) * log(k) * log(k))算法
http://stackoverflow.com/questions/5940420/find-kth-largest-ele
【在 g***s 的大作中提到】
: 这个是错的还是很明白的。不是单纯重复的问题
: 1 3 8
: 4 6 11
: 7 9 14
: 看样式矩阵，它每次都是在两个候选里面找小的。如果是v1,就往右走(不care下面的元
: 素）；如果是
: v2，就往下走（不care右边的元素）。这样才导致不会增加候选，否则，每次应该增加
: 两个（最多）候
: 选，k步最多是2k个元素。那么在候选里面挑最大（小）的元素，就不是一个O(1)了，
: 而需要heap来维
|
d*******l
发帖数: 338 | 29 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
【在 g**e 的大作中提到】
: 以前的讨论
: http://mitbbs.com/article_t/JobHunting/31611383.html
: stackoverflow上的人给出的O(sqrt(k) * log(k) * log(k))算法
: http://stackoverflow.com/questions/5940420/find-kth-largest-ele
|
g**e
发帖数: 6127 | 30 为啥？ log(k)^4 > k 呀
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
|
|
|
g***s
发帖数: 3811 | 31 好像不对
(1..9, 1), (1, 2..9) 这个就不是排序的。
1. (1..9, 1), (1, 2..9)
2. (2..4, 2), (2, 3..4)
3. (3, 3)
其实这个就是我在前文提的，第一行取k个，第2行取k/2个，..第k行取一个。这里面共
有klogk个元
素。这里面的1，2是排序的好像不对。
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
|
g**e
发帖数: 6127 | 32 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
【在 g***s 的大作中提到】
: 好像不对
: (1..9, 1), (1, 2..9) 这个就不是排序的。
: 1. (1..9, 1), (1, 2..9)
: 2. (2..4, 2), (2, 3..4)
: 3. (3, 3)
: 其实这个就是我在前文提的，第一行取k个，第2行取k/2个，..第k行取一个。这里面共
: 有klogk个元
: 素。这里面的1，2是排序的好像不对。
|
g***s
发帖数: 3811 | 33 哦。(1..9, 1), (1, 2..9)是两段。那就可以理解了
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
|
d*******l
发帖数: 338 | 34 没有这个就是比log(k)和k^(1/4)，而logn是o(n^d)的，对任意d都成立。也就是说logn
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
|
f*********i
发帖数: 197 | 35 Given two arrays A and B in ascending order with size m and n, respectively,
question:
find the Kth largest sum(a+b) where a in A and b in B, 1 |
g***s
发帖数: 3811 | 36 It is a Young Tableau.
easy to find a way using max-heap in O(klogk).
respectively,
【在 f*********i 的大作中提到】
: Given two arrays A and B in ascending order with size m and n, respectively,
: question:
: find the Kth largest sum(a+b) where a in A and b in B, 1
|
g*****k
发帖数: 623 | 37 I dont think it is a Young Tableau where column is sorted also.
and this questions seems have O(k) solution.
【在 g***s 的大作中提到】
: It is a Young Tableau.
: easy to find a way using max-heap in O(klogk).
:
: respectively,
|
g**e
发帖数: 6127 | 38 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
【在 g*****k 的大作中提到】
: I dont think it is a Young Tableau where column is sorted also.
: and this questions seems have O(k) solution.
|
g*****k
发帖数: 623 | 39 不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
This should be similiar to the above casee
}
}
【在 g**e 的大作中提到】
: 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
: 道怎么用。
: 这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
|
g***s
发帖数: 3811 | 40 I also think there is O(k) solution. since O(klogk) only uses the Young-
Tabeleau but the maxtrix of sum(a,b) is stonger than a Young-Tableleau.
Another way for O(klogk) (not using max-heap):
1. pickup k elements from first line:
2. pickup k/2 elements from 2nd line:
...
j. pickup k/j elements from jth line
...
k. pickup 1 elements from kth line
total number of elements is sum(1/j) < klogk. then find the kth, is
O(klogk).
It is still only uses the feature of Young-Tableleau, not sum-feature.
【在 g**e 的大作中提到】
: 这是个特殊的young tabeleau，每行和每列之间的差是个定值。但是这个特殊属性不知
: 道怎么用。
: 这个题我关注了一年了，版上讨论过三五次，没见过谁能给出O(k)算法的
|
|
|
g***s
发帖数: 3811 | 41 "题目没说每行和每列之间是个定值"
the delta values of each line are same.
a1+b1 a1+b2 a1+b3.... a1+bn
a2+b1 a2+b2 a2+b3.... a2+bn
delta values are {b_i - b_i-1}
【在 g*****k 的大作中提到】
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
|
g*****k
发帖数: 623 | 42 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair array1;
pair array2;
array1.first = 1;
array1.second = 2;
array2.first = 1;
array2.second =2;
size1 = m;
size2 = n;
res[0] = A[0]+B[0];
for (i=1; i
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1) {
array1.second = array2.first +1;
array1.first += 1;
}
else
array1.second+=1;
}
else {
This should be similiar to the above casee
}
}
【在 g*****k 的大作中提到】
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
|
g*****k
发帖数: 623 | 43 这里取a+b,a是来自A[]数组， b来自B[]数组。
没有完全看懂。
但是
if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
res[i] = A[array1.first]+B[array1.second;
if (array1.second = m - 1)
array1.second = array2.first +1;
else
array 1: 0 3 ....
array 2: 2 3 4....
array1[0] + array1[1] < array1[0] + array2[2] < array2[0] + array2[1]
array2[0] + array1[1] = array2[0] + array2[1]
看不出来array1[0] + array2[2] 怎么handle的.
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
|
g*****k
发帖数: 623 | 44 完整code
vector > findK(vector &v1, vector &v2, int k){
if (v1.empty() || v2.empty()) return vector >();
vector > res;
res.push_back(make_pair(0, 0));
pair a1(0, 1);
pair a2(0, 1);
for (int i = 1; i
if (v1[a1.first] + v2[a1.second] <= v2[a2.first] + v1[a2.second]) {
res.push_back(a1);
if (a1.second == v2.size() - 1){
a1.second = a2.first + 1;
a1.first += 1;
}
else {
a1.second += 1;
}
}
else {
res.push_back(make_pair(a2.second, a2.first));
if (a2.second == v1.size() - 1) {
a2.second = a1.first + 1;
a2.first += 1;
}
else {
a2.second += 1;
}
}
}
return res;
}
void print(vector > v)
{
for (int i = 0; i < v.size(); ++i) {
cout << "A[" << v[i].first << "] + B[" << v[i].second << "]"
<< endl;
}
}
【在 g*****k 的大作中提到】
: 这里取a+b,a是来自A[]数组， b来自B[]数组。
:
: 没有完全看懂。
: 但是
: if (A[array1.first]+B[array1.second]<=B[array2.first]+A[array2.second]){
: res[i] = A[array1.first]+B[array1.second;
: if (array1.second = m - 1)
: array1.second = array2.first +1;
: else
: array 1: 0 3 ....
|
g*****k
发帖数: 623 | 45 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
这完全没有必要
【在 g***s 的大作中提到】
: "题目没说每行和每列之间是个定值"
: the delta values of each line are same.
: a1+b1 a1+b2 a1+b3.... a1+bn
: a2+b1 a2+b2 a2+b3.... a2+bn
: delta values are {b_i - b_i-1}
|
g***s
发帖数: 3811 | 46 not correct.
{
【在 g*****k 的大作中提到】
: 完整code
: vector > findK(vector &v1, vector &v2, int k){
: if (v1.empty() || v2.empty()) return vector >();
: vector > res;
: res.push_back(make_pair(0, 0));
: pair a1(0, 1);
: pair a2(0, 1);
: for (int i = 1; i: if (v1[a1.first] + v2[a1.second] <= v2[a2.first] + v1[a2.second]) {
: res.push_back(a1);
|
g***s
发帖数: 3811 | 47 just use it to explain. not need to build matrix.
m(i,j) = a(i) + b(j). when we need it, just get it.
【在 g*****k 的大作中提到】
: 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
: 这完全没有必要
|
g**e
发帖数: 6127 | 48 this is wrong... try more samples, hehe
度。
不知
【在 g*****k 的大作中提到】
: 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
:
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair array1;
: pair array2;
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
|
g*****k
发帖数: 623 | 49 麻烦给各例子，好debug阿
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
|
g*****k
发帖数: 623 | 50 麻烦指出出错的地方哦
【在 g***s 的大作中提到】
: not correct.
:
: {
|
|
|
s*****y
发帖数: 897 | 51 同求，run了好几个例子，都是对的。
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
|
g***s
发帖数: 3811 | 52 很多元素都没用被检测而直接跳过了
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
|
g*****k
发帖数: 623 | 53 没问题啊，哪里错了？
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
|
g*****k
发帖数: 623 | 54 A[0]+A[1]不属于解，两个数必须分别属于两个数组。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
|
g*****k
发帖数: 623 | 55 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
|
g***s
发帖数: 3811 | 56 在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
|
g*****k
发帖数: 623 | 57 不明白，你说的再加一行指什么？
题目不是说给定两个数组找出第K大的a+b吗？
我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
这两个数组都是什么？
1 3 7
4 6 10
5 7 11
这个是对应的哪两个数组啊？
【在 g***s 的大作中提到】
: 在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
: 1 3 7
: 4 6 10
: 5 7 11
: 那么出来的就是1 3 4 6
|
d*******l
发帖数: 338 | 58 你这个想法倒是有可能是on the right track，不过目前的代码有问题吧，你试试A和B
都是1,2,3,4,5五个数，求第6个数就有问题啊
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
|
g***s
发帖数: 3811 | 59 a={1,4,7}
b={0,2,6}
k=4
your codes will output
1,3,4,7
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
|
d*******l
发帖数: 338 | 60 我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
|
|
|
g***s
发帖数: 3811 | 61 这个是错的还是很明白的。不是单纯重复的问题
1 3 8
4 6 11
7 9 14
看样式矩阵，它每次都是在两个候选里面找小的。如果是v1,就往右走(不care下面的元
素）；如果是
v2，就往下走（不care右边的元素）。这样才导致不会增加候选，否则，每次应该增加
两个（最多）候
选，k步最多是2k个元素。那么在候选里面挑最大（小）的元素，就不是一个O(1)了，
而需要heap来维
持，这就是为什么klogk
感觉O(k)的方法应该不需要把前k个元素一个一个列出来。
【在 d*******l 的大作中提到】
: 我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
: candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
: 也不敢说一定就不行，要证明是错的也并不必证明是对的容易
|
g**e
发帖数: 6127 | 62 以前的讨论
http://mitbbs.com/article_t/JobHunting/31611383.html
stackoverflow上的人给出的O(sqrt(k) * log(k) * log(k))算法
http://stackoverflow.com/questions/5940420/find-kth-largest-ele
【在 g***s 的大作中提到】
: 这个是错的还是很明白的。不是单纯重复的问题
: 1 3 8
: 4 6 11
: 7 9 14
: 看样式矩阵，它每次都是在两个候选里面找小的。如果是v1,就往右走(不care下面的元
: 素）；如果是
: v2，就往下走（不care右边的元素）。这样才导致不会增加候选，否则，每次应该增加
: 两个（最多）候
: 选，k步最多是2k个元素。那么在候选里面挑最大（小）的元素，就不是一个O(1)了，
: 而需要heap来维
|
d*******l
发帖数: 338 | 63 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
【在 g**e 的大作中提到】
: 以前的讨论
: http://mitbbs.com/article_t/JobHunting/31611383.html
: stackoverflow上的人给出的O(sqrt(k) * log(k) * log(k))算法
: http://stackoverflow.com/questions/5940420/find-kth-largest-ele
|
g**e
发帖数: 6127 | 64 为啥？ log(k)^4 > k 呀
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
|
g***s
发帖数: 3811 | 65 好像不对
(1..9, 1), (1, 2..9) 这个就不是排序的。
1. (1..9, 1), (1, 2..9)
2. (2..4, 2), (2, 3..4)
3. (3, 3)
其实这个就是我在前文提的，第一行取k个，第2行取k/2个，..第k行取一个。这里面共
有klogk个元
素。这里面的1，2是排序的好像不对。
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
|
g**e
发帖数: 6127 | 66 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
【在 g***s 的大作中提到】
: 好像不对
: (1..9, 1), (1, 2..9) 这个就不是排序的。
: 1. (1..9, 1), (1, 2..9)
: 2. (2..4, 2), (2, 3..4)
: 3. (3, 3)
: 其实这个就是我在前文提的，第一行取k个，第2行取k/2个，..第k行取一个。这里面共
: 有klogk个元
: 素。这里面的1，2是排序的好像不对。
|
g***s
发帖数: 3811 | 67 哦。(1..9, 1), (1, 2..9)是两段。那就可以理解了
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
|
d*******l
发帖数: 338 | 68 没有这个就是比log(k)和k^(1/4)，而logn是o(n^d)的，对任意d都成立。也就是说logn
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
|
C***U
发帖数: 2406 | 69 这个是咋得出来的？？？？
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
|
