AMAZON面试问题

Question

给定大小为K的N个阵列.对N个阵列中的这些K个元素中的每一个进行排序,这些N*K个元素中的每一个都是唯一的.从N个元素的所选子集中选择N个阵列中的每个阵列中的单个元素.减去最小和最大元素.现在,这个差异应该是最小可能的最小..希望问题很清楚:) :)

样品:

N=3, K=3

N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100

这里如果选择16,17,15 ..我们得到的最小差异为17-15 = 2.

Answer 1

我可以想到O(N*K*N)(在zivo正确指出之后编辑,现在不是一个很好的解决方案:()解决方案
.1.取N指针最初指向N个数组中的每一个的初始元素.

6, 16, 67
^ 
11,17,68
^
10, 15, 100
^ 

2.找出当前指针O(k)(6和11)中的最高和最低元素,并找出它们之间的差异.(5)
3.在该数组中将指向最低元素的指针递增1.

 6, 16, 67
    ^ 
 11,17,68
 ^
 10, 15, 100 (difference:5)
 ^ 

4.继续重复步骤2和3并存储最小差异.

 6, 16, 67
    ^ 
 11,17,68
 ^
 10,15,100 (difference:5)
    ^ 


 6, 16, 67
    ^ 
 11,17,68
    ^
 10,15,100 (difference:2)
    ^ 

以上将是必需的解决方案.

 6, 16, 67
    ^ 
 11,17,68
    ^
 10,15,100 (difference:84)
       ^ 

 6, 16, 67
        ^ 
 11,17,68
    ^
 10,15,100 (difference:83)
       ^ 

等等......

编辑:

通过使用堆(如Uri所建议的)可以减少其复杂性.我想到了它但遇到了一个问题:每次从堆中提取一个元素时,必须找到它的数组编号,以便增加该数组的相应指针.找到数组编号的有效方法肯定可以降低O(K*N log(K*N))的复杂度.一种天真的方式是使用这样的数据结构

Struct
{
    int element;
    int arraynumer;
}

并重建初始数据,如

 6|0,16|0,67|0

 11|1,17|1,68|1

 10|2,15|2,100|2

最初保留第一列的当前最大值并将指向的元素插入堆中.现在每次提取一个元素时,可以找到它的数组编号,该数组中的指针递增,新指向的元素可以与当前的最大值进行比较,并且可以相应地调整最大指针.