1

10個の数字のソートされていない整数配列で最初の繰り返し値を検索する最速の方法は何ですか?

配列に 1,000 万件のレコードがある場合の答えは何ですか?

4

3 に答える 3

2

私が考えることができる唯一の方法は、あなたが望むので2つの配列を使用することですfirst repetitive value in an unsorted integer

千万 ？？？記憶への影響がわからない

PHPDOCコメント

splFixedArrayのメモリフットプリントは、同じサイズの通常の「配列」の約37％です。もっと期待していたのですが、それも重要で、「パフォーマンス」ではなく、違いが見られると期待すべきところです。

PHP配列（および値）は実際にどのくらいの大きさですか？（ヒント：BIG！）

例

$array =  SplFixedArray::fromArray(array(1,2,4,6,4,2,7,7,3,3,1));
$list = array();
foreach ($array as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}

出力

 4
于 2012-10-12T13:36:37.213 に答える
1

これがベンチマークコードです。大きすぎてコメントに収まらなかったので、別の回答にしました。

<?php
$array = range(0, 10000);


$time_start = microtime(true);
$list = array();
foreach ( $array as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}
printf("Using foreach loop:<br/>%0.10f<br/><br/>", microtime(true)-$time_start);


$time_start = microtime(true);
$list = array();
foreach ( new ArrayIterator($array) as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}
printf("Using ArrayIterator:<br/>%0.10f<br/><br/>", microtime(true)-$time_start);

foreachループは よりも高速ですArrayIterator。

私は10000要素で試しました。要素は範囲関数で生成されていたため、すべての要素が異なる「最悪の」入力配列が確保されました。

私のマシンでは、100 万レコードの配列の生成に時間がかかりすぎました。

于 2012-10-12T18:28:29.453 に答える
1

最小の繰り返し数が必要な場合は、

  • O（n）時間で基数ソートを使用して配列をソートします

  • ソートされた配列をループし、最初の繰り返しを見つけます

配列がすでに存在する順序で最初の繰り返し番号が必要な場合

  • すでに存在するためにハッシュ セットに追加できない数値に到達するまで、ハッシュ セットに数値を追加する配列をループします。
于 2012-10-12T13:23:40.040 に答える