e*****e
发帖数: 1275 | 1 1. 给定M*N个不同的数，一共能生成多少个杨矩？如果允许数字有重复呢？
2. 给定杨矩，找k-th largest
（这题目我只有用最笨最蠢滴youngify 或者涂色法~~，有没有smart 的solution?)
可怜我想了好久（好久〉N天）也没想出好的solution.
那个谁谁谁，别老花精力把自己网站弄那么花哨~~~来来来。。。做题目~~ |
a******7
发帖数: 106 | 2 hehe i guess you are looking for ihave1337code
he has a post about searching in young matrix |
e*****e
发帖数: 1275 | 3 他那里只有search young tableau的~~~
就从左下角找啦~~~~~
这两题目也不知道是猴年马月哪个家伙提出来的，我郁闷了好久都没有想出方法 |
r********r
发帖数: 2912 | 4 What is "涂色法"
【在 e*****e 的大作中提到】
: 1. 给定M*N个不同的数，一共能生成多少个杨矩？如果允许数字有重复呢？
: 2. 给定杨矩，找k-th largest
: （这题目我只有用最笨最蠢滴youngify 或者涂色法~~，有没有smart 的solution?)
: 可怜我想了好久（好久〉N天）也没想出好的solution.
: 那个谁谁谁，别老花精力把自己网站弄那么花哨~~~来来来。。。做题目~~
|
e*****e
发帖数: 1275 | 5 就是把当前最大的涂上黑色,下一个最大就只能在黑色区域的边上~~~ |
f***g
发帖数: 214 | 6 2：
预备题目：已知一个数x，在young tab里面找，<=x的元素的个数。
这个是有O(n)算法的。
那么这道题，就有点类似于1-d数组找中位数的Order Statistics算法。
只不过，在一维中，用一个数字来记录当前位置。
在这里要用一个数组来记录当前位置。
以上是我的想法，以前版上也曾经有个人说过类似的思想。
从未写成代码。因为边界条件等等使这个题很复杂。 |
f***g
发帖数: 214 | 7 如果较真的话，给你两个ref
你能看懂了，研究明白了，麻烦给我讲讲。
1. http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html
2. google this paper:
Selection in X+Y and Matrices With Sorted Rows and Columns |
