एल्गोरिदम अधिकतम 1.5n तुलनाओं के साथ उच्च/निम्न संख्याओं को खोजने के लिए

Question

मैं इस होमवर्क प्रश्न के बारे में कुछ समय से सोच रहा हूं। आकार एन की एक संख्या सरणी को देखते हुए, एक एल्गोरिदम डिज़ाइन करें जो उच्च 1.5 और तुलनाओं के साथ उच्च और निम्न मानों को पायेगा।

मेरे पहली कोशिश थी

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

} 

मेरे समस्या पाश से प्रत्येक यात्रा तीन में से एक संभावनाएं है है:

• कम मूल्य पाया जाता है - 1 तुलना
• उच्च मूल्य बना पाया जाता है - 2 तुलना
• न तो पाया जाता है - 2 तुलना

तो एक संपूर्ण सरणी ट्रैवर्सल के लिए, अधिकतम 2 एन तुलना की जा सकती है, जो 1.5n तुलनाओं की अधिकतम आवश्यकता की समस्या से बहुत रोना है।

Answer 1

संख्याओं के जोड़े से शुरू करें और स्थानीय न्यूनतम और अधिकतम (एन/2 तुलना) खोजें। इसके बाद, एन/2 स्थानीय अधिकतम (एन/2 तुलना) से वैश्विक अधिकतम पाएं, और इसी तरह स्थानीय मिनटों (एन/2 तुलना) से वैश्विक मिनट। कुल तुलना: 3 * एन/2!

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons 

ध्यान दें कि उपर्युक्त समाधान सरणी को बदलता है। वैकल्पिक समाधान:

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i] 

Answer 2

यह ElKamina रूप में एक ही जवाब है, लेकिन मैं पहले से ही छद्म कोड मैंने सोचा कि मैं पूर्ण करने और इसे पोस्ट करता हूँ लिखना शुरू किया था के रूप में।

विचार उच्च मूल्यों की एक सरणी और कम मूल्यों की सरणी प्राप्त करने के लिए जोड़े मानों (एन/2 तुलना) की तुलना करना है। उन सभी सरणीओं के साथ हम क्रमशः उच्चतम और निम्नतम मान प्राप्त करने के लिए मूल्यों (2 * एन/2 तुलना) के जोड़े की तुलना करते हैं।

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
} 

इस कोड के लिए n भी नहीं किया जा रहा है या प्रारंभिक सरणी खाली किया जा रहा खाता नहीं करता है:

n/2 + 2*n/2 = 1.5n comparisons 

यहाँ स्यूडोकोड है।

Answer 3

यह एक प्रश्न है जो मैंने साक्षात्कार के दौरान किया था और मुझे साक्षात्कारकर्ता से एक छोटे संकेत के साथ जवाब मिला, जो "आप दो संख्याओं की तुलना कैसे करते हैं?" (यह वास्तव में मदद की)।

चलें कहते हैं कि मैं 100 नंबर (आप आसानी से n द्वारा यह जगह ले सकता है, लेकिन यह उदाहरण के लिए बेहतर काम करता है, तो n सम संख्या है):

यहाँ व्याख्या है। मैं क्या करता हूं कि मैं इसे 2 संख्याओं की 50 सूचियों में विभाजित करता हूं। प्रत्येक जोड़े के लिए मैं एक तुलना करता हूं और मैं कर चुका हूं (जो अब तक 50 तुलना करता है) तो मुझे केवल न्यूनतम न्यूनतम (जो 49 तुलना है) और अधिकतम अधिकतम (जो 49 तुलनाओं के साथ-साथ है)) जैसे कि हमें 49 + 49 + 50 = 148 तुलना करना है। हो गया था !

टिप्पणी: न्यूनतम हम (छद्म कोड में) इस प्रकार आगे बढ़ना लगता है:

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min; 

और हम (n-1) की तुलना में यह लगता है।कोड लगभग अधिकतम के लिए समान है।

Answer 4

मुझे पता है कि इसका पहले से ही उत्तर दिया गया है, लेकिन अगर कोई इस बारे में सोचने का एक और तरीका ढूंढ रहा है। यह उत्तर Lester's जैसा है, लेकिन बिना ब्रेक किए एन के विषम मानों को संभाल सकता है और अभी भी अधिकतम 1.5 एन तुलना करता है। रहस्य मॉड्यूलस में है। ;)

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

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]