洗马桶的问题# Living
f*i
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
question:
find the Kth largest sum(a+b) where a in A and b in B, 1
H*1
2 楼
如果连clorox都洗不干净的，是不是就只有换马桶了？
g*s
3 楼
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
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
e*3
4 楼
try Sno Bol. It is the best to clean up toilet.
g*k
5 楼
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,
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
6 楼
这是个特殊的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.
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出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
7 楼
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
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
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)算法的
那我不才，给出个想法，你看看是不是队的。
pair
pair
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
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
8 楼
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)算法的
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
9 楼
"题目没说每行和每列之间是个定值"
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;
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
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
g*k
10 楼
刚实验了一下，找到了个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
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;
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair
pair
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
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
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
g*k
11 楼
这里取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的.
没有完全看懂。
但是
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
12 楼
完整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
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 ....
vector
if (v1.empty() || v2.empty()) return vector
vector
res.push_back(make_pair(0, 0));
pair
pair
for (int i = 1; i
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
{
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
13 楼
晕倒，原来你的意思是用所有的加值构建出的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 的大作中提到】
: "题目没说每行和每列之间是个定值"
: 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
14 楼
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
: res.push_back(a1);
{
【在 g*****k 的大作中提到】
: 完整code
: vector
: if (v1.empty() || v2.empty()) return vector
: vector
: res.push_back(make_pair(0, 0));
: pair
: pair
: for (int i = 1; i
: res.push_back(a1);
g*s
15 楼
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啊。
: 这完全没有必要
m(i,j) = a(i) + b(j). when we need it, just get it.
【在 g*****k 的大作中提到】
: 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
: 这完全没有必要
g*e
16 楼
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 的大作中提到】
: 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
:
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
g*k
17 楼
麻烦给各例子，好debug阿
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
g*k
18 楼
麻烦指出出错的地方哦
【在 g***s 的大作中提到】
: not correct.
:
: {
【在 g***s 的大作中提到】
: not correct.
:
: {
s*y
19 楼
同求，run了好几个例子，都是对的。
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
g*s
20 楼
很多元素都没用被检测而直接跳过了
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
g*k
21 楼
没问题啊，哪里错了？
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
g*k
22 楼
A[0]+A[1]不属于解，两个数必须分别属于两个数组。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
g*k
23 楼
你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
g*s
24 楼
在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
g*k
25 楼
不明白，你说的再加一行指什么？
题目不是说给定两个数组找出第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
题目不是说给定两个数组找出第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
26 楼
你这个想法倒是有可能是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
: 这个是对应的哪两个数组啊？
都是1,2,3,4,5五个数，求第6个数就有问题啊
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
g*s
27 楼
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
: 这个是对应的哪两个数组啊？
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
28 楼
我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
g*s
29 楼
这个是错的还是很明白的。不是单纯重复的问题
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从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
: 也不敢说一定就不行，要证明是错的也并不必证明是对的容易
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
30 楼
以前的讨论
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来维
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
31 楼
那个方法对吗？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 的大作中提到】
: 以前的讨论
: 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
32 楼
为啥？ log(k)^4 > k 呀
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
g*s
33 楼
好像不对
(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)阶还低？
(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
34 楼
他这里说的似乎是坐标(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 的大作中提到】
: 好像不对
: (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
35 楼
哦。(1..9, 1), (1, 2..9)是两段。那就可以理解了
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
d*l
36 楼
没有这个就是比log(k)和k^(1/4)，而logn是o(n^d)的，对任意d都成立。也就是说logn
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
f*i
37 楼
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
question:
find the Kth largest sum(a+b) where a in A and b in B, 1
g*s
38 楼
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
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
39 楼
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,
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
40 楼
这是个特殊的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.
道怎么用。
这个题我关注了一年了，版上讨论过三五次，没见过谁能给出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
41 楼
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
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
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)算法的
那我不才，给出个想法，你看看是不是队的。
pair
pair
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
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
42 楼
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)算法的
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
43 楼
"题目没说每行和每列之间是个定值"
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;
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
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
g*k
44 楼
刚实验了一下，找到了个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
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;
不明白你说的，题目没说每行和每列之间是个定值。
那我不才，给出个想法，你看看是不是队的。
pair
pair
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
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
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
: size1 = m;
: size2 = n;
g*k
45 楼
这里取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了好几个例子，都是对的。
没有完全看懂。
但是
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
46 楼
完整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
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 ....
vector
if (v1.empty() || v2.empty()) return vector
vector
res.push_back(make_pair(0, 0));
pair
pair
for (int i = 1; i
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
{
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
47 楼
晕倒，原来你的意思是用所有的加值构建出的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 的大作中提到】
: "题目没说每行和每列之间是个定值"
: 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
48 楼
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
: res.push_back(a1);
{
【在 g*****k 的大作中提到】
: 完整code
: vector
: if (v1.empty() || v2.empty()) return vector
: vector
: res.push_back(make_pair(0, 0));
: pair
: pair
: for (int i = 1; i
: res.push_back(a1);
g*s
49 楼
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啊。
: 这完全没有必要
m(i,j) = a(i) + b(j). when we need it, just get it.
【在 g*****k 的大作中提到】
: 晕倒，原来你的意思是用所有的加值构建出的matrix啊。
: 这完全没有必要
g*e
50 楼
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 的大作中提到】
: 刚实验了一下，找到了个bug,现在修改了下，简单测试结果是对的，而且是O(K)复杂度。
:
: 不明白你说的，题目没说每行和每列之间是个定值。
: 那我不才，给出个想法，你看看是不是队的。
: pair
: pair
: array1.first = 1;
: array1.second = 2;
: array2.first = 1;
: array2.second =2;
g*k
51 楼
麻烦给各例子，好debug阿
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
【在 g**e 的大作中提到】
: this is wrong... try more samples, hehe
:
: 度。
: 不知
g*k
52 楼
麻烦指出出错的地方哦
【在 g***s 的大作中提到】
: not correct.
:
: {
【在 g***s 的大作中提到】
: not correct.
:
: {
s*y
53 楼
同求，run了好几个例子，都是对的。
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
g*s
54 楼
很多元素都没用被检测而直接跳过了
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
1 4
0 2 6
对应的杨氏
1 3 7
4 6 10
【在 g*****k 的大作中提到】
: 麻烦指出出错的地方哦
g*k
55 楼
没问题啊，哪里错了？
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
g*k
56 楼
A[0]+A[1]不属于解，两个数必须分别属于两个数组。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
【在 s*****y 的大作中提到】
: 同求，run了好几个例子，都是对的。
g*k
57 楼
你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
【在 g***s 的大作中提到】
: 很多元素都没用被检测而直接跳过了
: 1 4
: 0 2 6
: 对应的杨氏
: 1 3 7
: 4 6 10
g*s
58 楼
在火车上看的。没看仔细。你的else部分居然不对称。所以要再加一行。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
1 3 7
4 6 10
5 7 11
那么出来的就是1 3 4 6
【在 g*****k 的大作中提到】
: 你是不是没运行我的code阿？输出结果完全是对的阿。而且这些全都被检测了。
g*k
59 楼
不明白，你说的再加一行指什么？
题目不是说给定两个数组找出第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
题目不是说给定两个数组找出第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
60 楼
你这个想法倒是有可能是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
: 这个是对应的哪两个数组啊？
都是1,2,3,4,5五个数，求第6个数就有问题啊
【在 g*****k 的大作中提到】
: 不明白，你说的再加一行指什么？
: 题目不是说给定两个数组找出第K大的a+b吗？
: 我运行了不少test,得出的结果都是对的啊。所以想知道你找出的错误的例子。
: 这两个数组都是什么？
: 1 3 7
: 4 6 10
: 5 7 11
: 这个是对应的哪两个数组啊？
g*s
61 楼
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
: 这个是对应的哪两个数组啊？
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
62 楼
我觉得这个方法如果失败，最大的原因就是解不了重复。总觉得第k个值只有两个
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
candidates从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
也不敢说一定就不行，要证明是错的也并不必证明是对的容易
【在 g***s 的大作中提到】
: a={1,4,7}
: b={0,2,6}
: k=4
: your codes will output
: 1,3,4,7
g*s
63 楼
这个是错的还是很明白的。不是单纯重复的问题
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从直觉上说不通，在重复非常多的情况下，这个方法可能有本质缺陷。不过
: 也不敢说一定就不行，要证明是错的也并不必证明是对的容易
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
64 楼
以前的讨论
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来维
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
65 楼
那个方法对吗？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 的大作中提到】
: 以前的讨论
: 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
66 楼
为啥？ log(k)^4 > k 呀
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
【在 d*******l 的大作中提到】
: 那个方法对吗？O(sqrt(k) * log(k) * log(k))岂不是比O(k)阶还低？
g*s
67 楼
好像不对
(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)阶还低？
(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
68 楼
他这里说的似乎是坐标(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 的大作中提到】
: 好像不对
: (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
69 楼
哦。(1..9, 1), (1, 2..9)是两段。那就可以理解了
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
我开始以为说是一段
【在 g**e 的大作中提到】
: 他这里说的似乎是坐标(1..9,1)是(1,1),(2,1)...(9,1)
d*l
70 楼
没有这个就是比log(k)和k^(1/4)，而logn是o(n^d)的，对任意d都成立。也就是说logn
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
小于n的任意小次方的。所以那个复杂度比O(k)还低。。
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
C*U
71 楼
这个是咋得出来的？？？？
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
【在 g**e 的大作中提到】
: 为啥？ log(k)^4 > k 呀
相关阅读
顶级 rice cooker抽油烟机的神器在lowes有卖吗有人知道waterproof地下室要多少钱吗？站了5个小时的梯子揭墙纸请教大家是在哪里买床 (转载)要不要从了ADT?再也不要自己刷楼梯，累死我了好耻辱，竟然就借我1W6，怎么办啊？一般大家都买那种人寿保险啊？电高压锅的deal $69有没有卖金色家电的Nest thermostat 1st gen $49.50 lowes吐个槽：看了大半年的房子竟然一个offer都没给过这个遮阳伞怎么样啊哪里有修地毯的公司急求lowes 10%off的胖有没有人用过equityplus program?圣诞节是不是偷老中的最佳季节啊哪去买圣诞树贷款的point和rebate