Sonuç tespit edilmesi için etkin bir algoritma

7 Cevap php

Ben tamsayılar N boyutlu bir dizi eşit değerleri tespit etmek için etkili bir algoritma için arıyorum. Bu maçların endeksleri dönmelidir.

Ne yazık ki, ben iki döngüler ile o kaba kuvvet daha akıllı bir şey düşünemiyorum.

Any help will be appreciated. Thanks!

7 Cevap

Sen dizi kesiştiği olabilir. Bu dizi1 olan dizi2 tüm değerlerini bulur

$array1 = array("a" => "green", "b" => "brown", "c" => "blue", "red");
$array2 = array("a" => "green", "yellow", "red");
$result_array = array_intersect_assoc($array1, $array2);
print_r($result_array);

Dönecekti

Array
(
    [a] => green
)

Bu maçlar anahtarları ve değerleri ile tüm bir dizi döndürür. Temelde array_insert_assoc argüman sonsuz sayıda sağlayabilir:

array_intersect_assoc($base_array, $arr1, $arr2 ...);

Bu $base_array tüm sonraki dizilerde olan değerleri arar. Bu anahtar ve değer $base_array alınacak demektir

Ayrıca kullanarak anahtarları karşılaştırmak olabilir:

array_intersect_keys($base_array, $arr1, $arr2, $arr3);

Bu döngüler O (N ^ 2) vardır. N büyük mü? Eğer öyleyse, dizi O (NlogN) sıralayabilir, sonra (N) O tarayın? ... Ya da ben bir şey eksik?

Sen son değerleri tutmak için bir dizi kullanabilirsiniz. Örneğin,

results = empty list
set = empty set
foreach key, val in array:
   if val is not in set: add val to set
   else: add key to results
return results

Her setin bakmak O (1) olduğunu, bu nedenle yerine O (n ^ 2) ve O (n) bu algo olacak sonuçlar iç içe döngü kullanılması durumunda.

Eğer (tablodaki karşılık gelen anahtarın) değer ve değer endeksleri listesi olduğunu bu dizide 1, 2, 3, 3, 2, 1 Eğer tuşu ile bir karma tablo kullanabilirsiniz gibi multi-rastlama takip etmek istiyorum. Verilen dizi için sonuç lik {01:00, 5 bakacağız; 1, 4,: 2 3: 2, 3}.

results = empty hashtable
for each key, val in array:
    if val is not in results:
        results[val] = new list()
    results[val].append(key)
return results

Belki de bu?

$arr = array_map('unserialize', array_unique(array_map('serialize', $arr)));

Sorusu Gönderen: How to remove duplicated 2-dimension array in PHP? 

if ($arr !== array_map('unserialize', array_unique(array_map('serialize', $arr))))
{
    // found duplicates
}

Her öğe için yine tüm dizi üzerinden gitmek zorunda değilsiniz. Sadece dizideki alt öğe ile bir öğe testi:

$array = /* huge array */;
$size = count($array);
for($i = 0; $i < $size; $i++)
{
    for($j = $i + 1; $j < $size; $j++) // only test with the elements after $i
    {
        if($array[$i] == $array[$j])
            return true; // found a duplicate
    }
    return false; // found no duplicate
}

Bu aklıma gelebilecek en etkili yoludur. Olacak gibi ihtiyaca göre uyarlayın.

Dizilerinize biri makul statik ise bunu ters olabilir (ki siz aynı diziyi birkaç kez karşılaştıran olduğunu).

O değere göre anahtarlı ve gerçek diziye dizini döndürür başka dizi ayarlanır.

$invert = array();
foreach ($cmptoarray as $ix => $ival) {
   $invert[$ival] = $ix;
}

Sonra sadece numarasını kontrol için if ( isset($invert[$compfrmarray[$i]) ) .... gerekir.

Not: Eğer aynı dizide karşı birkaç kez karşılaştıracak olursak bunu yaparken sadece değer!

Sadece onun dizine değer eşleme ilişkilendirilebilir bir dizi kullanın:

foreach($array1 as $index => $value) {
    $aa[$value] = $index;
}

foreach($array2 as $index => $value) {
    if(isset($aa[$value])) {
        echo 'Duplicate:  .  Index 1:  '.$aa[$value].'  Index 2:  '.$index.'.';
    }
}

etiketler