ओ (लॉग एन) समय में लगातार पूर्णांक की सरणी में डुप्लिकेट तत्व पाएं

Question

कुछ दिन पहले, एक साक्षात्कार में मुझे एक ऐसे कार्यक्रम के लिए कहा गया था जिसमें O(log n) समय में लगातार पूर्णांक सरणी में एकल डुप्लिकेट तत्व मिलेगा ।

मामला कुछ हद तक विशिष्ट है, क्योंकि कुल 11 पूर्णांक (1 से 10, उस क्रम में) प्लस, इनमें से किसी भी संख्या का एक डुप्लिकेट, बीच में कहीं भी डाला गया है।

मैं एक नमूना इस के समान दिया गया था:

{1, 2, 3, 4, 5, 6, , 7, 8, 9, 10}

#include <stdio.h> 

int main (void) 
{ 
    int a[11] = {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}, first=0, last=10, mid; 

    while (1) 
    { 
     mid = (first + last)/2; 

     if (mid+1 == a[mid]) 
      first = mid+1; 

     else if ((mid == 0) || (mid == 10) || (a[mid+1] - a[mid-1] == 1)) /* Order is Important, (a[mid+1] - a[mid-1] == 1) must be last */ 
      break; 

     else 
      last = mid-1; 
    } 

    printf("Duplicate element is %d, located at position no. %d.", a[mid], mid+1); 

    return 0; 
} 

इस ठीक से O(log n) मानदंडों को पूरा करेंगे: तो, अब मैं निम्नलिखित सी कोड के साथ आ गया है? और, क्या इस पर कोई विकल्प/सुधार हैं?

Answer 1

हां, इसमें O(log n) समय जटिलता है।

यह निम्न तथ्य का उपयोग कर कोड और अधिक स्पष्ट करना संभव है: यदि आप पता लगाने के लिए छोटी से छोटी i ऐसी है कि a[i] != i + 1 की जरूरत है ताकि यह एक अधिक संक्षिप्त तरीके से लागू किया जा सकता:

//invariant: the [0...low] prefix does not contain a duplicate 
//   the [0...high] prefix contains a duplicate 
low = 0 //[0...0] prefix obviously does not contain a duplicate 
high = 10 //the entire array obviously contains a duplicate 
while high - low > 1: 
    mid = (low + high)/2 
    if a[mid] != mid + 1: 
     high = mid 
    else: 
     low = mid 
print(a[high], high) 

Answer 2

हम संशोधित कर सकते हैं समाधान प्राप्त करने के लिए binary search algorithm। binary search में, हमारे पास एक कुंजी है और हमने सरणी आकार को विभाजित करके अपनी स्थिति खोजने के लिए इस कुंजी का उपयोग किया। यहां, हमारे पास कोई कुंजी नहीं है, इसके बजाय हमें इसे ढूंढना है। लेकिन duplicate element का व्यवहार bisect सरणी आकार में उपयोग किया जा सकता है। कैसे ? की सुविधा देता है देखें:

ध्यान से डेटा देख, हम आसानी से देख सकते हैं कि लगातार तत्व सरणी में यादृच्छिक स्थिति में डुप्लिकेट तत्व डालने (माना index) तत्वों की संपत्ति बदल जाएगा (a[i] == i+1 ->a[i] != i+1) के बाद की स्थिति से index (index सहित)। अब इस बदली हुई संपत्ति का उपयोग सरणी आकार को विभाजित करने के लिए किया जा सकता है। इसलिए, हम O(log(n)) में डुप्लिकेट पा सकते हैं।

उदाहरण के लिए, पर विचार करें आपके दिए गए सरणी: {1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10}

{1, 2, 3, 4, 5, 6, 2, 7, 8, 9, 10} 
          || 
          from this position the the property of (a[i] == i+1) will no more satisfied. 

यह गुण समाधान में सरणी आकार द्विभाजित करने के लिए मॉडल हो सकता है।

void binary_duplictae_finder(int a[], int low, int high) { 

    int mid=(low+high)/2; 

    if(high - low > 1){ 
      if(a[mid]!=mid+1) 
       binary_duplictae_finder(a, low, mid); 
      else 
       binary_duplictae_finder(a, mid, high); 
    } 

    if(high==low+1) 
     printf("%d ", a[high]); 
}