d********t
发帖数: 9628 | 1 N组整数，每组都由小到大排列，如何快速找出N组都有的最大数？ |
p*****2
发帖数: 21240 | 2 从后往前找，当前数最大值的往前走。一直走到大家数值都相等。 |
d********t
发帖数: 9628 | 3 兔爷就是牛
【在 p*****2 的大作中提到】
: 从后往前找，当前数最大值的往前走。一直走到大家数值都相等。
|
p*****2
发帖数: 21240 | 4
好久没见你了。已经开始上班了？
【在 d********t 的大作中提到】
: 兔爷就是牛
|
d********t
发帖数: 9628 | 5 上班很久了感觉，人生彻底绝望。
【在 p*****2 的大作中提到】
:
: 好久没见你了。已经开始上班了？
|
c***p
发帖数: 221 | 6 N-way merge with order from large to small. stop when find equal value for
all sequences, or any sequence run out.
【在 d********t 的大作中提到】
: N组整数，每组都由小到大排列，如何快速找出N组都有的最大数？
|
S*******w
发帖数: 24236 | 7 纽约妞很多
泡几个就不绝望了
【在 d********t 的大作中提到】
: 上班很久了感觉，人生彻底绝望。
|
d********t
发帖数: 9628 | 8 人家一听偶IT打杂男就不理不睬了。
【在 S*******w 的大作中提到】
: 纽约妞很多
: 泡几个就不绝望了
|
S*******w
发帖数: 24236 | 9 是个男的就行了吧
【在 d********t 的大作中提到】
: 人家一听偶IT打杂男就不理不睬了。
|
d********t
发帖数: 9628 | 10 哈哈，你想得挺美啊。
【在 S*******w 的大作中提到】
: 是个男的就行了吧
|
|
|
S*******w
发帖数: 24236 | 11 帅就行了
【在 d********t 的大作中提到】
: 哈哈，你想得挺美啊。
|
d********t
发帖数: 9628 | 12 矮丑穷
【在 S*******w 的大作中提到】
: 帅就行了
|
Z*****Z
发帖数: 723 | 13 我觉得直接上K way merge可能不是最优的。
假设N个数组，每个数组里有N个数，一共有N^2个数，（最大）堆的size也是N。Kway m
erge的复杂度是O(N^2 * lgN)
如果不用堆，而用一个size 为N的数组存储N个指针，每个指针指向自己的数组，可以做
到O（N2）
【在 c***p 的大作中提到】
: N-way merge with order from large to small. stop when find equal value for
: all sequences, or any sequence run out.
|
Z*****Z
发帖数: 723 | 14 上代码。
static int findCommon(int[][] intArrs){
if(intArrs == null || intArrs.length == 0){
return -1;
}
for(int[] arr : intArrs){
if(arr == null || arr.length == 0){
return -1;
}
}
int[] pointers = new int[intArrs.length];
int ans = intArrs[0][0];
boolean found = false;
while(!found){
found = true;
for(int i = 0; i < intArrs.length; i ++){
int p = pointers[i];
while(p < intArrs[i].length && intArrs[i][p] < ans){
p ++;
}
pointers[i] = p;
if(p >= intArrs[i].length){
return -1; // no such element
}
if(intArrs[i][p] > ans){
ans = intArrs[i][p];
found = false;
}
}
}
return ans;
}
public static void main(String[] args) {
int[][] intArrs = {
{1, 3, 5, 7, 9},
{2, 4, 6, 7, 10},
{1, 2, 3, 5, 7, 9},
};
System.out.println(findCommon(intArrs));
}
m
以做
【在 Z*****Z 的大作中提到】
: 我觉得直接上K way merge可能不是最优的。
: 假设N个数组，每个数组里有N个数，一共有N^2个数，（最大）堆的size也是N。Kway m
: erge的复杂度是O(N^2 * lgN)
: 如果不用堆，而用一个size 为N的数组存储N个指针，每个指针指向自己的数组，可以做
: 到O（N2）
|
p*****2
发帖数: 21240 | 15
m
以做
这个算法不错呀。我发现你玩指针数组很牛呀。
【在 Z*****Z 的大作中提到】
: 我觉得直接上K way merge可能不是最优的。
: 假设N个数组，每个数组里有N个数，一共有N^2个数，（最大）堆的size也是N。Kway m
: erge的复杂度是O(N^2 * lgN)
: 如果不用堆，而用一个size 为N的数组存储N个指针，每个指针指向自己的数组，可以做
: 到O（N2）
|
Z*****Z
发帖数: 723 | 16 其实就这一招。。。被二爷发现了。。。
【在 p*****2 的大作中提到】
:
: m
: 以做
: 这个算法不错呀。我发现你玩指针数组很牛呀。
|
p*****2
发帖数: 21240 | 17
哈哈。偷学了。见你这么用两次了。
【在 Z*****Z 的大作中提到】
: 其实就这一招。。。被二爷发现了。。。
|
Z*****Z
发帖数: 723 | 18 二爷法眼，一针见血
【在 p*****2 的大作中提到】
:
: 哈哈。偷学了。见你这么用两次了。
|
c***p
发帖数: 221 | 19 cool! 用heap的确浪费时间了, 每排除1个数要花费logN个比较。
学习了！
如果时间复杂度允许是O(N^2 * lgN)，那么空间复杂度可以降到O(1)。
m
以做
【在 Z*****Z 的大作中提到】
: 我觉得直接上K way merge可能不是最优的。
: 假设N个数组，每个数组里有N个数，一共有N^2个数，（最大）堆的size也是N。Kway m
: erge的复杂度是O(N^2 * lgN)
: 如果不用堆，而用一个size 为N的数组存储N个指针，每个指针指向自己的数组，可以做
: 到O（N2）
|
e****e
发帖数: 418 | 20
Thanks for your idea, erYe. Here is the code.
public static int findMaxInEveryArray(int[][] m) {
if ( m == null || m.length == 0 )
return -1;
int[] pointers = new int[m.length];
for( int i = 0; i < m.length; i++ ){
if ( m[i] == null || m[i].length == 0 ) {
return -1;
}
pointers[i] = m[i].length -1;
}
while ( true ) {
if ( isAllEqual( m, pointers ) )
break;
int maxIndex = indexOfMaxNumberInPointerArray( m, pointers );
if ( maxIndex < 0 )
return -1;
else
pointers[maxIndex]--;
}
return m[0][pointers[0]];
}
public static boolean isAllEqual(int[][] m, int[] pointers) {
int first = m[0][pointers[0]];
for ( int i = 1; i < pointers.length; i++ ) {
if ( m[i][pointers[i]] != first ) {
return false;
}
}
return true;
}
public static int indexOfMaxNumberInPointerArray(int[][] m, int[]
pointers) {
int maxIdx = 0;
int max = Integer.MIN_VALUE;
for ( int i = 0; i < pointers.length; i++ ) {
if ( m[i][pointers[i]] > max ) {
max = m[i][pointers[i]];
maxIdx = i;
}
}
return maxIdx;
}
【在 p*****2 的大作中提到】
: 从后往前找，当前数最大值的往前走。一直走到大家数值都相等。
|
d********t
发帖数: 9628 | 21 idea很棒，可惜有bug。如果各个数组都是1开头，你的指针都动不了。
【在 Z*****Z 的大作中提到】
: 上代码。
: static int findCommon(int[][] intArrs){
:
: if(intArrs == null || intArrs.length == 0){
: return -1;
: }
:
: for(int[] arr : intArrs){
: if(arr == null || arr.length == 0){
: return -1;
|
Z*****Z
发帖数: 723 | 22 我找的是最小的那个common元素
【在 d********t 的大作中提到】
: idea很棒，可惜有bug。如果各个数组都是1开头，你的指针都动不了。
|
