केवल 8 तुलनाओं के साथ 8 संख्याओं की सरणी में सबसे छोटा और दूसरा सबसे छोटा नंबर खोजें

Question

यह एक साक्षात्कार प्रश्न है जिसका मुझे जवाब देना था। वास्तव में एक दोस्त वास्तव में लेकिन उसने मुझसे पूछा और मुझे जवाब भी नहीं पता था। इसलिए मैं यहां पूछ रहा हूं:

8 पूर्णांकों की एक श्रृंखला को देखते हुए, केवल 9 तुलनाओं का उपयोग करके सबसे छोटा और दूसरा सबसे छोटा पूर्णांक ढूंढें। अधिक विशेष रूप से n+log(n)-2 समय में।

मुझे यकीन है कि आप केवल 9 तुलनाओं का उपयोग करके इसे कैसे कर सकते हैं। यह कितना करीब आ गया है। (10 तुलना)

public class Comp { 
    static int[] nums = new int[]{9, 4, 5, 3, 2, 7, 6, 1}; 
    static int compcount = 0; 

    //int[] is nums[] array 
    public static int[] twoLeast(int[] a){ 
     int min1 = a[0]; //Prospective lowest number 
     int min2 = a[1]; //Prospective second lowest number 

     if(isLessThan(min2, min1)){ 
      min1 = a[1]; 
      min2 = a[0]; 
     } 

     for(int i=2; i<a.length;i++){ 
      if(isLessThan(a[i], min1)){ 
       min2 = min1; 
       min1 = a[i]; 
      }else if(isLessThan(a[i], min2)){ 
       min2 = a[i]; 
      } 
     } 

     return new int[]{min1, min2}; 
    } 

    public static boolean isLessThan(int num1, int num2){ 
     compcount++; 
     return num1 < num2; 
    } 
} 

यहाँ मैं एक समारोह isLessThan() तुलना की संख्या का ट्रैक रखने के लिए है। फिर से, यह 10 तुलना करता है। 9 तुलनाओं में इसे कैसे करना संभव है। या n+log(n)-2 समय में?

पुनश्च: मैं यह जावा में लागू है, लेकिन यह किसी भी

Answer 1

समाधान के बारे में सोचने का एक तरीका यह एक टेनिस नॉक-ऑफ प्रतियोगिता श्रृंखला की तरह है। मान लें कि प्रत्येक नंबर किसी खिलाड़ी से मेल खाता है। नंबर बंद जोड़ी और प्रत्येक खेल एक जोड़ी के भीतर संख्याओं के बीच एक तुलना के अनुरूप हैं:

गेम्स: (a1,a2), (a3, a4), (a5, a6), (a7, a8)

विजेता: a12, a34, a56, a78

गेम्स: (a12, a34), (a56, a78)

विजेता: a1234, a5678

खेल: (a1234, a5678)

विजेता: a12345678

खेल की संख्या = 7 ==>(n - 1)

दूसरा सबसे अच्छा केवल विजेता से हार किया गया होगा। मान लीजिए a3 विजेता है। फिर दूसरा सबसे अच्छा a4, a12 या a5678 होगा।

गेम्स: (a4, a12)

विजेता: a412

गेम्स: a(412, 5678)

विजेता: a4125678

तो हम दूसरा सबसे अच्छा ==>(lg(n) - 1)

के लिए 2 खेल है इसलिए खेलों की संख्या = 012

   a12345678 
      /  \ 
      /   \ 
      /   \ 
     /    \ 
     a1234   a5678 
    / \   / \ 
    /  \  / \ 
    a12  a34  a56  a78 
/ \ / \ / \ /\ 
a1  a2 a3 a4 a5 a6 a7 a8 

तो a3 विजेता है, हमने::

    a3 
        | 
       /----|----\ 
      /   \ 
      /   \ 
     /    \ 
      a3 >==========> a5678 
    / \   / \ 
    /  \  / \ 
    a12 <====< a3  a56  a78 
/ \ / \ / \ /\ 
a1  a2 a3 ->a4 a5 a6 a7 a8 

असल में अंतिम विजेता a3 एक चल गया होगा= (n + lg(n) - 2)

यह ऊपर प्रतियोगिता एक पेड़ कल्पना करने के लिए आसान है पत्ती से रूट तक पथ (lg(n) -1)। अपने रास्ते में, वह दूसरे सर्वश्रेष्ठ खिलाड़ी को हरा देंगे, जो {a4, a12, a5678} में से एक है। इसलिए हम केवल यह पता लगा सकते हैं कि वर्णित विजेता के अलावा पथ में अधिकतम अधिकतम देखकर दूसरा सबसे अच्छा कौन है।

Answer 2

एक संकेत के रूप में भाषा, में खेलने के लिए सरणी के तत्वों के लिए एक उन्मूलन टूर्नामेंट ब्रैकेट स्थापित किया जा सकता सरणी में सबसे बड़ी संख्या जीतेंगे। टूर्नामेंट, और यदि आपको दो की शक्ति है तो आपको केवल एन -1 तुलना की आवश्यकता होगी।

दूसरा सबसे बड़ा तत्व केवल सबसे बड़ा खो गया होगा, और टूर्नामेंट में सबसे बड़ा तत्व केवल लॉग इन अन्य तत्वों को हरा देता है। उन तत्वों का एक दूसरा उन्मूलन टूर्नामेंट खेलें, जहां सबसे बड़ा तत्व ढूंढें, जिसके लिए लॉग एन -1 तुलना की आवश्यकता है।

कुल मिलाकर, केवल एन + लॉग एन - 2 कुल तुलना की आवश्यकता है। जो कुछ भी बचा है उसे कोड करना है।

आशा है कि इससे मदद मिलती है!