0

あるインタビューでこの質問をされたことがあります。私は主に、O(n^2) よりも優れた時間で 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];
}

どうやら (私が彼の期待する解決策を示していたとしたら) 2 次元配列内の個々の配列が既にソートされているという仮定を利用していたでしょう。上記の解決策は、私のインタビュアーを納得させませんでした。

では、上記のクラスを O(n^2) よりも効率的な方法で使用して、期待される出力を生成するにはどうすればよいでしょうか?

PS: A) サンプル入力内の個々の配列は常にソートされることに注意してください。B) 入力には重複があり、出力には重複が含まれている必要があります。

4

2 に答える 2

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) に比例して時間がかかります。

詳細については、ウィキペディアのヒープ (データ構造)を参照してください。または、より長い説明が必要な場合は、優先キューとヒープに関する一連のブログ投稿をお読みください。コード例は C# で書かれていますが、最初の 2 つの記事はコードに依存しません。

于 2014-02-23T05:51:22.060 に答える