केवल 0s n 1s

Question

से युक्त सरणी को सॉर्ट करने के लिए अत्यधिक अनुकूलित अलगो मुझे केवल 0s n 1s वाली सरणी को सॉर्ट करने के लिए एक अत्यधिक अनुकूलित अलगो ढूंढना होगा।

समाधान का मेरा संस्करण नंबर गिनना है। शून्य (एक्स कहें) और वाले (वाई कहें)। एक बार ऐसा करने के बाद, सरणी में x शून्य को y 1s के बाद रखें। यह ओ (एन) बनाता है।

कोई भी अलगो जो इससे बेहतर चलता है ??? साक्षात्कार में मुझसे यह सवाल पूछा गया था।

Answer 1

चूंकि आपको n इनपुट तत्वों में से प्रत्येक की जांच करनी है, तो आप O(n) पर सुधार नहीं कर सकते हैं।

इसके अलावा, चूंकि आपके एल्गोरिदम को O(1) मेमोरी की आवश्यकता है, तो आप उस पर सुधार नहीं कर सकते हैं (O(1) से असम्बद्ध रूप से बेहतर कुछ भी नहीं है)।

Answer 2

यदि आप सरणी को जोड़ते हैं, तो आपके पास 1 की संख्या, थोड़ा अधिक कुशल हो सकती है, लेकिन फिर भी ओ (एन) हो सकती है।

Answer 3

आप ओ (एन) से अधिक कुशल नहीं हो सकते हैं क्योंकि प्रत्येक आइटम का निरीक्षण किया जाना चाहिए।

Answer 4

हम किस प्रकार की "सरणी" के बारे में बात कर रहे हैं? अगर हम 16-बिट हस्ताक्षरित पूर्णांक में बिट्स को गिनना चाहते थे तो कई ओ (1) समय एल्गोरिदम विकसित किए गए हैं: Fast Bit Count Routines देखें।

यह वहां प्रस्तुत एल्गोरिदम में से एक है; एक वे निफ्टी समानांतर गणना फोन:

#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

हम हे (एन) की तुलना में बेहतर नहीं कर सकता है, लेकिन लगता है कि हम एक पास में कर सकते हैं लग रहा है

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

यह एक एकल की तरह लगता है रॉड abacus प्रकार। अब मैं उत्सुक हूं कि आपका साक्षात्कारकर्ता कौन था।

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