0

我曾经在一次采访中被问到这个问题，我对最佳答案感到好奇。我主要受困于提供一种在比 O(n^2) 更好的时间内跟踪二维数组的解决方案。这是问题：

/*
Here's a helper class that can efficiently return the smallest
object it contains. Assume it magically knows how to sort your
objects correctly.
*/

@interface MinHeap : NSObject

@property (readonly) NSUInteger count;

// Adds an object
- (void)addObject:(id)object;

// Returns (but does not remove) the smallest object, or nil if empty
- (id)minObject;

// Removes and returns the smallest object, or nil if empty
- (id)popMinObject;

// Removes all objects
- (void)removeAllObjects;

// **Implement this method**
- (NSArray*)process:(NSArray*)incomingArray
@end

/*
Sample input:
[ 
  [ @2, @4, @6 ],
  [ @1, @5, @10 ],
  [ @3, @7, @8, @98, @99 ],
  [],
  [ @4, @4 ]
]

Expected output:
[ @1, @2, @3, @4, @4, @4, @5, @6, @7, @8, @10, @98, @99 ]
*/

这是我给出的答案：

- (NSArray*)process:(NSArray*)incomingArray
{
    // n squared
    for (int i=0; i<incomingArray.count; i++)
    {
        NSArray* row = incomingArray[i];

        for (int j=0; j<row.count; j++)
            [self addObject:row[j]];
    }

    NSMutableArray* returnArray = [NSMutableArray new];

    // n
    for (int i=0; i<self.count; i++)
        [returnArray addObject:[self minObject]];

    return [NSArray arrayWithArray:returnArray];
}

显然（如果我给出了他预期的解决方案）我会利用二维数组中的各个数组已经排序的假设。上述解决方案并没有说服我的面试官。

那么，如何以比 O(n^2) 高效的方式使用上述类来产生预期的输出？

PS：A）请注意，样本输入中的各个数组始终是排序的。B）输入可以有重复，输出应该包含重复。

4

2 回答 2

1

如果您有一个可以在 O(1) 时间内返回最小元素的神奇数据结构，那么只需将所有元素添加到堆中并从最小到最大弹出它们。

于 2014-02-23T03:17:14.977 回答
1

如果您有一个实现该MinHeap接口的对象，那么您可以像这样构建一个 O(n log n) 排序。请注意，这是伪代码。

// first, build the heap
heap = new MinHeap();
for each item in the source array
    heap.addObject(item);

// now, repeatedly remove the minimum item until there are no more items
while (heap.count > 0)
    outputArray.Add(heap.popMinObject);

将项目插入堆需要 O(log n) 时间，其中 n 是当前在堆上的项目数。从堆中删除最小项需要 O(log n) 时间。因此，这种使用堆对数组进行排序的方法所花费的时间与 2*(n log n) 成正比。

有关详细信息，请参阅Wikipedia 上的堆（数据结构）。或者，如果您想要更冗长的解释，请阅读我关于优先级队列和堆的一系列博客文章。代码示例在 C# 中，但前两篇文章与代码无关。

于 2014-02-23T05:51:22.060 回答