अधिकतर एन + लॉग₂ (एन) -2 तुलनाओं में सरणी में दूसरा सबसे बड़ा नंबर खोजें

Question

आपको एन विशिष्ट संख्याओं की एक अनसुलझा सरणी इनपुट के रूप में दिया जाता है, जहां एन 2 की शक्ति है। एक एल्गोरिदम दें जो दूसरे सबसे बड़े की पहचान करता है सरणी में संख्या, और यह अधिकांश n + log₂ (n) -2 तुलनाओं पर उपयोग करता है।

Answer 1

1. विषम और यहां तक ​​कि पदों में एन तत्व सरणी के तत्वों की तुलना करने और प्रत्येक जोड़ी का सबसे बड़ा तत्व निर्धारित करने के साथ प्रारंभ करें। इस चरण के लिए एन/2 तुलना की आवश्यकता है। अब आपके पास केवल n/2 तत्व हैं। एन/4, एन/8, ... तत्व प्राप्त करने के लिए जोड़ी की तुलना जारी रखें। रोकें जब सबसे बड़ा तत्व पाया जाता है। इस चरण के लिए कुल एन/2 + एन/4 + एन/8 + ... + 1 = एन -1 तुलना की आवश्यकता है।
2. पिछले चरण के दौरान, सबसे बड़ा तत्व तुरंत log₂ (n) अन्य तत्वों से तुलना की गई थी। आप log₂ (n) -1 तुलना में इन तत्वों में से सबसे बड़ा निर्धारित कर सकते हैं। यह सरणी में दूसरी सबसे बड़ी संख्या होगी।

---

उदाहरण: 8 नंबर [10,9,5,4,11,100,120,110] की सरणी।

स्तर 1 पर तुलना: [10, 9] -> 10 [5,4] -> 5, [11,100] -> 100, [120,110] -> 120।

स्तर 2 पर तुलना: [10,5] -> 10 [100,120] -> 120।

स्तर 3: पर तुलना [10,120] -> 120।

अधिकतम 120 है। इसकी तुरंत तुलना की गई: 10 (स्तर 3 पर), 100 (स्तर 2 पर), 110 (स्तर 1 पर)।

चरण 2 को अधिकतम 10, 100, और 110 मिलना चाहिए। 110 है। यह दूसरा सबसे बड़ा तत्व है।

Answer 2

समस्या यह है: मान लें, तुलना स्तर 1 में, एल्गोरिदम को सभी सरणी तत्व को याद रखने की आवश्यकता है क्योंकि सबसे बड़ा अभी तक ज्ञात नहीं है, फिर, दूसरा, आखिरकार, तीसरा। असाइनमेंट के माध्यम से इन तत्वों को ट्रैक रखने के द्वारा अतिरिक्त मूल्य असाइनमेंट का आह्वान किया जाएगा और बाद में जब सबसे बड़ा ज्ञात है, तो आपको ट्रैकिंग को वापस लेने की भी आवश्यकता है। नतीजतन, यह सरल 2 एन -2 तुलना एल्गोरिदम से काफी तेज नहीं होगा। इसके अलावा, क्योंकि कोड अधिक जटिल है, आपको संभावित डीबगिंग समय के बारे में भी सोचने की आवश्यकता है।
जैसे: PHP में, तुलना बनाम मूल्य कार्य के लिए समय चल रहा है मोटे तौर पर किया जाता है: तुलना: (11-19) मूल्य काम करने के लिए: 16.

Answer 3

I shall give some examples for better understanding. : 
example 1 : 
>12 56 98 12 76 34 97 23 
>>(12 56) (98 12) (76 34) (97 23) 
>>> 56 98 76 97 
>>>> (56 98) (76 97) 
>>>>> 98 97 
>>>>>> 98 

The largest element is 98 

Now compare with lost ones of the largest element 98. 97 will be the second largest. 

Answer 4

nlogn कार्यान्वयन

 public class Test { 
      public static void main(String...args){ 
       int arr[] = new int[]{1,2,2,3,3,4,9,5, 100 , 101, 1, 2, 1000, 102, 2,2,2}; 
       System.out.println(getMax(arr, 0, 16)); 
      } 

     public static Holder getMax(int[] arr, int start, int end){ 
      if (start == end) 
      return new Holder(arr[start], Integer.MIN_VALUE); 
     else { 
      int mid = (start + end)/2; 
      Holder l = getMax(arr, start, mid); 
      Holder r = getMax(arr, mid + 1, end); 

      if (l.compareTo(r) > 0) 
      return new Holder(l.high(), r.high() > l.low() ? r.high() : l.low()); 
      else 
      return new Holder(r.high(), l.high() > r.low() ? l.high(): r.low()); 
     } 
     } 

    static class Holder implements Comparable<Holder> { 
     private int low, high; 
     public Holder(int r, int l){low = l; high = r;} 

    public String toString(){ 
     return String.format("Max: %d, SecMax: %d", high, low); 
    } 

    public int compareTo(Holder data){ 
     if (high == data.high) 
     return 0; 

     if (high > data.high) 
     return 1; 
     else 
     return -1; 
    } 

    public int high(){ 
     return high; 
    } 
    public int low(){ 
     return low; 
    } 
    } 

} 

Answer 5

public static int FindSecondLargest(int[] input) 
     { 
      Dictionary<int, List<int>> dictWinnerLoser = new Dictionary<int, List<int>>();//Keeps track of loosers with winners 
      List<int> lstWinners = null; 
      List<int> lstLoosers = null; 

      int winner = 0; 
      int looser = 0; 

      while (input.Count() > 1)//Runs till we get max in the array 
      { 
       lstWinners = new List<int>();//Keeps track of winners of each run, as we have to run with winners of each run till we get one winner 

       for (int i = 0; i < input.Count() - 1; i += 2) 
       { 
        if (input[i] > input[i + 1]) 
        { 
         winner = input[i]; 
         looser = input[i + 1]; 
        } 
        else 
        { 
         winner = input[i + 1]; 
         looser = input[i]; 
        } 

        lstWinners.Add(winner); 


        if (!dictWinnerLoser.ContainsKey(winner)) 
        { 
         lstLoosers = new List<int>(); 
         lstLoosers.Add(looser); 
         dictWinnerLoser.Add(winner, lstLoosers); 
        } 
        else 
        { 
         lstLoosers = dictWinnerLoser[winner]; 
         lstLoosers.Add(looser); 
         dictWinnerLoser[winner] = lstLoosers; 
        } 
       } 

       input = lstWinners.ToArray();//run the loop again with winners 
      } 

      List<int> loosersOfWinner = dictWinnerLoser[input[0]];//Gives all the elemetns who lost to max element of array, input array now has only one element which is actually the max of the array 

      winner = 0; 

      for (int i = 0; i < loosersOfWinner.Count(); i++)//Now max in the lossers of winner will give second largest 
      { 
       if (winner < loosersOfWinner[i]) 
       { 
        winner = loosersOfWinner[i]; 
       } 
      } 

      return winner; 
     } 

Answer 6

दिए गए सरणी के लिए इस हैशिंग एल्गोरिदम का उपयोग क्यों न करें [n]? यह सी * एन चलाता है, जहां सी चेक और हैश के लिए निरंतर समय है। और यह एन तुलना करता है।

int first = 0; 
    int second = 0; 
    for(int i = 0; i < n; i++) { 
     if(array[i] > first) { 
      second = first; 
      first = array[i]; 
     } 
    } 

या हूँ मैं सिर्फ सवाल समझ में नहीं आता ...

Answer 7

Python2.7 में: निम्नलिखित कोड अतिरिक्त प्रकार के लिए ओ (nlog लॉग एन) पर काम करता है। कोई अनुकूलन?

def secondLargest(testList): 
    secondList = [] 
    # Iterate through the list 
    while(len(testList) > 1): 
     left = testList[0::2] 
     right = testList[1::2] 

     if (len(testList) % 2 == 1): 
      right.append(0) 

     myzip = zip(left,right) 
     mymax = [ max(list(val)) for val in myzip ] 
     myzip.sort() 
     secondMax = [x for x in myzip[-1] if x != max(mymax)][0] 

     if (secondMax != 0): 
      secondList.append(secondMax) 
     testList = mymax 

    return max(secondList) 

Answer 8

मैंने जावा में इस एल्गोरिदम को @Evgeny Kluev द्वारा उत्तर दिया है। कुल तुलना एन + लॉग 2 (एन) -2 हैं। एक अच्छा संदर्भ भी है: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec03.349.pdf। यह शीर्ष मतदान एल्गोरिदम के समान है। आशा है कि मेरा समाधान सहायक होगा। धन्यवाद।

public class op1 { 

private static int findSecondRecursive(int n, int[] A){ 
    int[] firstCompared = findMaxTournament(0, n-1, A); //n-1 comparisons; 
    int[] secondCompared = findMaxTournament(2, firstCompared[0]-1, firstCompared); //log2(n)-1 comparisons. 
    //Total comparisons: n+log2(n)-2; 
    return secondCompared[1]; 
} 

private static int[] findMaxTournament(int low, int high, int[] A){ 
    if(low == high){ 
     int[] compared = new int[2]; 
     compared[0] = 2; 
     compared[1] = A[low]; 
     return compared; 
    } 
    int[] compared1 = findMaxTournament(low, (low+high)/2, A); 
    int[] compared2 = findMaxTournament((low+high)/2+1, high, A); 
    if(compared1[1] > compared2[1]){ 
     int k = compared1[0] + 1; 
     int[] newcompared1 = new int[k]; 
     System.arraycopy(compared1, 0, newcompared1, 0, compared1[0]); 
     newcompared1[0] = k; 
     newcompared1[k-1] = compared2[1]; 
     return newcompared1; 
    } 
    int k = compared2[0] + 1; 
    int[] newcompared2 = new int[k]; 
    System.arraycopy(compared2, 0, newcompared2, 0, compared2[0]); 
    newcompared2[0] = k; 
    newcompared2[k-1] = compared1[1]; 
    return newcompared2; 
} 

private static void printarray(int[] a){ 
    for(int i:a){ 
     System.out.print(i + " "); 
    } 
    System.out.println(); 
} 

public static void main(String[] args) { 
    //Demo. 
    System.out.println("Origial array: "); 
    int[] A = {10,4,5,8,7,2,12,3,1,6,9,11}; 
    printarray(A); 
    int secondMax = findSecondRecursive(A.length,A); 
    Arrays.sort(A); 
    System.out.println("Sorted array(for check use): "); 
    printarray(A); 
    System.out.println("Second largest number in A: " + secondMax); 
} 

}