sadece 0s n 1s

Question

'dan oluşan bir diziyi sıralamak için yüksek düzeyde optimize edilmiş algo Sadece 0sn1s'den oluşan bir diziyi sıralamak için yüksek düzeyde optimize edilmiş bir algo bulmam gerekiyor.

Çözüme ait sürümüm, no. sıfırlar (x demek) ve olanlar (y deyin). Bunu yaptıktan sonra diziye x sıfırları, ardından y 1 yerleştirin. Bu onu yapar O (n).

Bundan daha iyi çalışan herhangi bir algo ??? Bu soruyu röportajda sordum.

Answer 1

n giriş öğelerinin her birini incelemeniz gerektiğinden, O(n) numaralı telefonu geliştiremezsiniz. Ayrıca, algoritmanızın O(1) belleğe gereksinim duyması nedeniyle, bunu geliştiremezsiniz (O(1)'dan daha asimptotik olarak daha iyi bir şey yoktur).

Answer 2

Diziyi özetliyorsanız, 1'lerin sayısı biraz daha verimli olabilir, ancak yine de O (n).

Answer 3

Her öğenin denetlenmesi gerektiğinden, O (N) 'den daha verimli olamazsınız.

Answer 4

Ne tür bir "dizi" hakkında konuşuyoruz? Eğer bitleri 16 bit işaretsiz bir tamsayı olarak saysaydık, o zaman birkaç O (1) zaman algoritması geliştirildi: bkz. Fast Bit Count Routines.

Bu, orada sunulan algoritmalardan biridir; biri onlar Şık Paralel Kont çağırır:

#define MASK_01010101 (((unsigned int)(-1))/3) 
#define MASK_00110011 (((unsigned int)(-1))/5) 
#define MASK_00001111 (((unsigned int)(-1))/17) 
int bitcount (unsigned int n) { 
    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101); 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011); 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111); 
    return n % 255 ; 
} 

Answer 5

biz O (n) daha iyi yapamaz, ama bir geçişte yapabileceği gibi

low = 0; 
high = arr.length - 1; 

while (low < high) { 
    while (arr[low] == 0) { 
     low ++; 
    } 
    while (arr[high] == 1) { 
     high --; 
    } 
    if (low < high) { 
    //swap arr[low], arr[high] 
    } 
} 

Answer 6

Bu tek benziyor görünüyor çubuk abaküs sıralaması. Şimdi, görüşmecinizin kim olduğunu merak ediyorum.

http://www.dangermouse.net/esoteric/abacussort.html