j**l 发帖数: 2911 | 1 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中
一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个
pair。这道题有O(n)的算法么?
这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C
的每行每列都是严格升序排列的,所以C是一个Young Tableau
虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n
个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度
小于这个新问题? 也就是原问题和新问题,不是等价的。 | r****o 发帖数: 1950 | 2 问一下,Young Tableau是怎么定义的?是不是每行每列都顺序递增就是Young Tableau?
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| k***e 发帖数: 556 | 3 这也太难了
不搞combinatorial的人连啥是young tableau都不知道
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| m*****g 发帖数: 226 | | Z*****Z 发帖数: 723 | 5 Young Tableau的情况可以用最小堆做到nlgn吗?
btw:数组可以转化到YT,但是YT不一定能转化回去吧?
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| S*******n 发帖数: 1867 | 6 两个问题不等价
这个问题只是Young tableau的一个特殊情况
就是说一个young tableau 问题不能转化为这个问题
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| j**l 发帖数: 2911 | 7 是的,这个Young Tableau比较特殊,也就是说每行的差量是一样的,每列的差量也是
一样的
【在 S*******n 的大作中提到】 : 两个问题不等价 : 这个问题只是Young tableau的一个特殊情况 : 就是说一个young tableau 问题不能转化为这个问题 : : C : 小n
| j**l 发帖数: 2911 | 8 那么,在行差量相同和列差量相同的Young Tableau中,应该可以O(n)找出前n个最小? | S*******n 发帖数: 1867 | 9 你这个题和mergeSort里面那个merge函数有点相似
如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿
总的运算应该还是n..因为只找n个..
vector(int) vecForResult=vector(n,0);
vecForResult[0]=A[0]+B[0];
int i=1;
int indexA=0,indexB=0;
while(i
{
bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
if(isMoveB==1)
{
vecForResult[i]=A[indexA]+B[indexB+1];
indexB++;
}
else
{
vecForResult[i]=A[indexA+1]+B[indexB];
indexA++;
}
i++;
}
correct me if I am wrong
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| S*******n 发帖数: 1867 | 10 刚刚写了一个解法 在下面
我觉得把这个换为Young tableau的问题换复杂了
【在 j**l 的大作中提到】 : 那么,在行差量相同和列差量相同的Young Tableau中,应该可以O(n)找出前n个最小?
| | | j**l 发帖数: 2911 | 11 画图比较直观
A = 1, 2, 3, 4
B = 5, 6, 7, 8
则C是
6 7 8 9
7 8 9 10
8 9 10 11
9 10 11 12
则任何顺序能打印这16个和的程序应该输出
6 7 7 8 8 8 9 9 9 9 10 10 10 11 11 12
前4个是6 7 7 8
【在 S*******n 的大作中提到】 : 刚刚写了一个解法 在下面 : 我觉得把这个换为Young tableau的问题换复杂了
| D***h 发帖数: 183 | 12 你好像喜欢把简单问题复杂化? 不过我喜欢你的发散思维.
直接simulate merge sort不就是O(n)了。
C
小n
【在 j**l 的大作中提到】 : 原题是这样的,数组A和数组B的长度都是n, 且都严格单调递增,取A中一个元素和B中 : 一个元素组成一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个 : pair。这道题有O(n)的算法么? : 这道题实际上是可以转换成Young Tableau的,定义C[i][j] = A[i] + B[j], 则矩阵C : 的每行每列都是严格升序排列的,所以C是一个Young Tableau : 虽然C让问题看去很直观,但大小为n x n的Young Tableau是做不到O(n)时间取得最小n : 个元素的吧?或许原题可以转换为这个新问题,但能找到一个更巧妙的方法,其复杂度 : 小于这个新问题? 也就是原问题和新问题,不是等价的。
| j**l 发帖数: 2911 | 13 A = {1, 2, 3, 4};
B = {5, 6, 7, 8};
应该输出{6, 7, 7, 8}
为何输出{6, 7, 8, 9}?
【在 S*******n 的大作中提到】 : 你这个题和mergeSort里面那个merge函数有点相似 : 如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿 : 总的运算应该还是n..因为只找n个.. : vector(int) vecForResult=vector(n,0); : vecForResult[0]=A[0]+B[0]; : int i=1; : int indexA=0,indexB=0; : while(i: { : bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
| h**k 发帖数: 3368 | 14 算法不对,简单的说你这个算法无法比较
A[i1]+B[j1] 和 A[i2]+B[j2], if i1>i2 and j1j2.
【在 S*******n 的大作中提到】 : 你这个题和mergeSort里面那个merge函数有点相似 : 如果题目的意思是A(B)里面的数不能和A(B)自身的数配对的话 这个题应该很好解阿 : 总的运算应该还是n..因为只找n个.. : vector(int) vecForResult=vector(n,0); : vecForResult[0]=A[0]+B[0]; : int i=1; : int indexA=0,indexB=0; : while(i: { : bool isMoveB= A[indexA]+B[indexB+1]<= A[indexA+1]+B[indexB];
| h**k 发帖数: 3368 | 15 恩,直接用heap可以实现O(nlogn)
这个和是一个partial order,(x,y)表示A[x]+B[y],则
从(0,0)开始,把(0,0)存入heap of size n,
输出heap中的最大值,然后把(0,1)和(1,0)放入heap,再输出最大值。
suppose the maximum element in the heap is (i,j),remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题,(i,j)可能会被放入heap两次,解决方法,
给每个(i,j)设一个counter,initial value = 0, every time we want to put (i,j)
into the heap, check the counter's value, if it = 0, just increase it by 1,
otherwise put it into the heap;
【在 Z*****Z 的大作中提到】 : Young Tableau的情况可以用最小堆做到nlgn吗? : btw:数组可以转化到YT,但是YT不一定能转化回去吧? : : C : 小n
| a*s 发帖数: 425 | 16 这个问题,我可以想到的最有效的方法是
先找最小的pair,
比如
A=[1,2,3,4]
B=[5,6,7,8]
然后最小的肯定是A 和 B的第一个元素相加,
然后,就相当于
找
A1=[2,3,4]
B1=[5,6,7,8]
OR
A2=[1,2,3,4]
B2=[6,7,8]
这两个组的最小,
有点像二分树的情况,
一个pair,共有n^2个pair。每个pair对两个元素求和,找出和最小的n个pair。
每行每列都是严格升序排列的,所以C是一个Young Tableau。问题化归为,如何在一个
Young Tableau中找到前n个最小元素?
实际上,矩阵C这个Young Tableau是比较特殊的,我们注意到每一行的增量相同,每一
列的增量也相同。所以如果不附加这个特性到Young Tableau, 则原问题和新问题不是
等价的。
问题,应该是等价的。
【在 j**l 的大作中提到】 : A = {1, 2, 3, 4}; : B = {5, 6, 7, 8}; : 应该输出{6, 7, 7, 8} : 为何输出{6, 7, 8, 9}?
|
|