Mark sıralanmamış bir dizi üst N elemanları

5 Cevap php

Ben (oluşturulan kalıp rulo) sıralanmamış bir dizi var, ve ben (sort-ve-kelepir ile önemsiz) bunun üst N öğeleri seçmek istiyorum, ama düzen onları tutarak işaretleyin.

Örneğin:

mark([1,2,3,4], 3) ==> [[1, false], [2, true], [3, true], [4, true]]

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], [2, false], [6, true], [2, false]]

Dizi 1 kadar herhangi bir değerleri içerir ve herhangi bir uzunlukta olabilir ve işaretli elemanların miktarı değişkendir olabilir.

Ile yaşayabilir

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], 2, [6, true], [2, true]]

(Yani, işaretsiz gitmek için yanlış işaretlenmiş olurdu numaraları), ama ben daha çok bunu önlemek istiyorum.

Ne mecburidir dizinin sırası değişmeden kalır olmasıdır.

Üst elemanları tekrarlanır ise (örneğin: [6,6,6,6,6,6] üst 3), ilk 3 öğeleri işaretlemek.

(Karmaşıklık çok önemli değil N yeterince küçük.)

DÜZENLEME: Bonus noktası: "top" ve "alt" modu arasında geçiş yapmak için bir parametre ekleyin.

5 Cevap

Şu anda kabul edilen yanıt giriş listesi m kere tarar. Bu bir sadece iki kez tarar. O (n * m) vs O (n). Sen bir yığın veri yapısı gerekir. İşte Python olduğunu.

import heapq

def mark(data, n):
    top = heapq.nlargest(n, ((value, index) for index, value in enumerate(data)))
    indexes = set(value[1] for value in top)
    return [[value, index in indexes] for index, value in enumerate(data)]

print mark([1, 2, 3, 4], 3)
print mark([3, 5, 2, 6, 2], 3)

Çıktı:

[[1, False], [2, True], [3, True], [4, True]]
[[3, True], [5, True], [2, False], [6, True], [2, False]]

Ben soru PHP etiketli çünkü biz, burada PHP bahsediyoruz varsayalım. Eğer uygulamaya çalışacağız herhangi bir akıllı algoritma yerleşik fonksiyonunu kullanarak daha yavaş olacaktır. Yani userspace numaralarını çatırdayan iyi değil, PHP böyle çalıştığını.

Peki ne yapmanız gerekiyor çeşit dizinin bir kopyasını ve üst N elemanlarının tuşları kaydetmek, daha sonra dizi yineleme ve işareti elemanları dedi. Ama bir nokta vardır: PHP'nin tür istikrarlı değildir. Hangi bağları durumunda elemanlarının konumlarını kullanmak istiyorsanız, bunu kendiniz yapmanız gerekecek demektir. Peki yerine böyle asort() or arsort() , you'll have to use array_multisort() gibi bir işlevi kullanarak.

Sonuç şudur:

function mark(array $arr, $n, $order = SORT_DESC)
{
    $keys = $values = $position = array();

    $i = 0;
    foreach ($arr as $k => $v)
    {
        $keys[]     = $k;
        $values[]   = $v;
        $position[] = $i;

        ++$i;
    }

    // sort values in given $order, use their position as tiebreaker (always in ascending order)
    array_multisort($values, $order, $position, SORT_ASC, $keys);
    $mark = array_flip(array_slice($keys, 0, $n));

    $ret = array();
    foreach ($arr as $k => $v)
    {
        $ret[] = array($v, isset($mark[$k]));
    }

    return $ret;
}

Hangi üretir

SORT_DESC
[3,6,6,6,6,6,2] => [[3,false],[6,true],[6,true],[6,true],[6,false],[6,false],[2,false]]
[3,5,2,6,2]     => [[3,true],[5,true],[2,false],[6,true],[2,false]]

SORT_ASC
[3,6,6,6,6,6,2] => [[3,true],[6,true],[6,false],[6,false],[6,false],[6,false],[2,true]]
[3,5,2,6,2]     => [[3,true],[5,false],[2,true],[6,false],[2,true]]

Sen endeksleri bir dizi quick select algoritma kullanabilir. Yerine manipüle dizide geçti, sen endekslerin düzeni işlemek ve sonra bu lineer zaman alacağını üst N. işaret ediyorum.

Bu madde karmaşıklık için yeterince küçük değilse: (psuedocode)

for(int m = 0; m < mark_count; m++) {
    highest = MIN_INT;
    highestindex = -1;
    foreach i in array:
        if array[i] > highest && is_unmarked(i)
            highest = array[i]
            highestindex = i;
    mark(i)
}

EDIT: yerine alt olanları bulmak MAX_INT bizim sayaç başlar ve dizideki değeri ondan daha az olduğunu kontrol etmek isterseniz.

Ve mark() ve örnek uygulamaları istiyorsanız is_unmarked:

function mark(i) {
    array[i] = [array[i], true];
}

function is_unmarked(i) {
    if (array[i] is array & array[i][1] == true)
        return false;
    return true;
}

(Emin is Ben onu beklediğiniz gibi çalışır Değil - ister ama anlamı açıktır, umarım)

Şu şekilde gerekirse bu optimize olacaktır. Optimize edilmesi gerekir yoksa o zaman ne olacak yapmak.

  1. Dizi N "üst N" değerinden daha küçük ise, tüm DOĞRU işaretleyin. O (N)
  2. arr öğeleri geçmesi ve aynı zamanda üst N öğelerin arr pozisyonları ve değerlerinin bir listesini tutmak ise tüm yanlış işaretlemek. Ayrıca yalnızca / kontrol N. öğe karşı karşılaştırmak, düşük, greater(topN[N-1], arr[i]) gerekir. arr[0] üzerinde yineleme zaman topn N doldururken iken arr[N-1] N halen en düşük tutarak, dolana kadar sadece üst N listesine eklemek için bir koşul olmalıdır alt. O (arr.size())
  3. Şimdi tüm üst N liste üzerinde yanlış bir döngü olarak işaretlenebilir ve üst N. O olduğu gibi gerçek olarak (N) arr pozisyonlarına geri ve işareti gitmek olduğunu

Bu nedenle, genel maliyeti O olduğu (N + arr.size())

etiketler