ios - 用于在 Objective-C 中对二维数组进行排序的优于 O(n^2) 的算法

Question

我在一次采访中被问到这个问题，我很好奇最佳答案是什么。我主要坚持提供一种解决方案，该解决方案可以在比 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) 更高效的方式使用上述类来产生预期的输出？

P.S: A) 请注意，示例输入中的各个数组始终已排序。 B) 输入可以有重复项，输出应该包含重复项。

Answer 1

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