रैखिक समय से बेहतर में तीन गुना खोजें जैसे कि ए [एन -1]> = ए [एन] <= ए [एन + 1]

Question

A[0] >= A[1] और A[N-1] >= A[N-2] जैसे साक्षात्कार में संख्याओं का अनुक्रम दिया गया था। मुझे कम से कम एक तिहाई जैसे A[n-1] >= A[n] <= A[n+1] खोजने के लिए कहा गया था।

मैंने पुनरावृत्तियों में हल करने की कोशिश की। साक्षात्कारकर्ता रैखिक समय समाधान से बेहतर उम्मीद की। मुझे इस प्रश्न से कैसे संपर्क करना चाहिए?

उदाहरण: 9 8 5 4 3 2 6 7

उत्तर: 3 2 6

Answer 1

रैखिक तुम सिर्फ सेट के माध्यम से पुनरावृत्ति, उन सब की तुलना द्वारा कर सकता है।

आप पहले दो की ढलान भी देख सकते हैं, फिर एक प्रकार का बाइनरी काट/क्रमशः ट्रैवर्सल जोड़ों की तुलना में जब तक आपको विपरीत ढलान में से कोई एक न मिल जाए। यह n समय से बेहतर के लिए amortize होगा, मुझे लगता है, हालांकि इसकी गारंटी नहीं है।

संपादित करें: बस एहसास हुआ कि आपके आदेश का क्या अर्थ है। द्विआधारी काट विधि <n समय में ऐसा करने की गारंटी है, क्योंकि परिवर्तन की बात होने की गारंटी है (यह मानते हुए कि आपकी N-1, N-2 सूची के अंतिम दो तत्व हैं)। यह आपको सिर्फ उस स्थिति में द्विआधारी काट उर्फ ​​डिवाइड & जीत का उपयोग कर O(logn) समय में आदेश log(n)

Answer 2

हम इस हल कर सकते हैं में यह करना होगा इसे खोजने/उनमें से एक की जरूरत है, इसका मतलब है। द्विआधारी खोज। रैखिक समय से बेहतर है। तो हमें एक तिगुना खोजने की जरूरत है जैसे कि A[n-1] >= A[n] <= A[n+1]।

पहले दिए गए सरणी के मध्य को ढूंढें। यदि मध्य अपने बाएं से छोटा है और इसके दाएं से बड़ा है। फिर वापस आओ, आपका जवाब है। संयोग से यह आपके रिकर्सन में बेसकेस होगा। इसके अलावा यदि len(arr) < 3 भी वापस आते हैं। एक और बेसकेस।

अब रिकर्सन परिदृश्य आता है। जब रिकर्स करना है, तो हमें और अधिकार का निरीक्षण करना होगा। इसके लिए, यदि मध्य बाईं ओर तत्व से अधिक है तो सरणी के बाईं ओर एक उपप्रोबल के रूप में छोड़ने पर विचार करें और इस नई सरणी के साथ पुनर्संरचना करें। यानी इस बिंदु पर मूर्त शब्दों में हमारे पास ...2... इंडेक्स n 6 के साथ होगा। इसलिए हम बाईं ओर जाते हैं यह देखने के लिए कि 2 के बाईं ओर वाला तत्व ट्रिपलेट पूरा करता है या नहीं।

अन्यथा यदि मध्य अपने दाएं उपराष्ट्रय पर तत्व से अधिक है तो सरणी के दाहिने ओर 1 + को उपप्रोबलेम और रिकर्स के रूप में मानें।

---

अधिक थ्योरी: उपरोक्त समस्या को समझने लेकिन पर पढ़ने के लिए पर्याप्त होना चाहिए। तत्वों के दिए गए सेट में स्थानीय मिनीमा खोजने के लिए समस्या अनिवार्य रूप से उबलती है। सरणी में एक संख्या को स्थानीय मिनीमा कहा जाता है यदि यह दोनों बाएं और दाएं संख्याओं से छोटा होता है जो ठीक से A[n-1] >= A[n] <= A[n+1] तक उबाल जाता है।

एक दिया गया सरणी जैसे कि इसके पहले 2 तत्व घट रहे हैं और अंतिम 2 तत्व बढ़ रहे हैं स्थानीय मिनीमा होने के लिए। ऐसा क्यों है? आइए इसे अस्वीकार करके साबित करें। यदि पहले दो नंबर कम हो रहे हैं, और कोई स्थानीय न्यूनतम नहीं है, तो इसका मतलब है कि तीसरा नंबर दूसरे नंबर से कम है। अन्यथा दूसरा नंबर स्थानीय न्यूनतम होगा। उसी तर्क के बाद चौथी संख्या तीसरे नंबर से कम होनी चाहिए और इसी तरह आगे भी। इसलिए सरणी में संख्या घटते क्रम में होनी चाहिए।जो बढ़ते क्रम में पिछले दो संख्याओं की बाधा का उल्लंघन करता है। यह अस्वीकार करता है कि स्थानीय न्यूनतम होने की आवश्यकता है।

उपर्युक्त सिद्धांत O(n) रैखिक दृष्टिकोण का सुझाव देता है लेकिन हम निश्चित रूप से बेहतर कर सकते हैं। लेकिन सिद्धांत निश्चित रूप से हमें समस्या के बारे में एक अलग परिप्रेक्ष्य देता है।

---

कोड: यहाँ अजगर कोड है (FYI - stackoverflow पाठ संपादक मुक्तहस्त में टाइप किया गया था, यह misbheave सकता है)।

def local_minima(arr, start, end): 
    mid = (start+end)/2 

    if mid-2 < 0 and mid+1 >= len(arr): 
     return -1; 

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it! 
     return mid-1; 

    if arr[mid-1] > arr[mid-2]: 
     return local_minima(arr, start, mid); 
    else: 
     return local_minima(arr, mid, end); 

ध्यान दें कि मैं सिर्फ n की अनुक्रमणिका लौटाता हूं। ट्रिपल को प्रिंट करने के लिए केवल -1 और +1 लौटाए गए इंडेक्स में करें। source

Answer 3

ऐसा लगता है कि तुम क्या कह रहे हैं की तरह यह है:

आप संख्या का एक अनुक्रम है। यह घटता शुरू होता है और तत्व n तक घटता रहता है, फिर यह अनुक्रम के अंत तक बढ़ने लगता है। n खोजें।

यह एक (गैर इष्टतम) रैखिक समय में समाधान है:

for (i = 1; i < length(A) - 1; i++) 
{ 
    if ((A[i-1] >= A[i]) && (A[i] <= A[i+1])) 
     return i; 
} 

रैखिक समय की तुलना में बेहतर करने के लिए, आपको जानकारी है कि आप इस बात से मिलता है कि श्रृंखला कम हो जाती है तो बढ़ जाती है प्रयोग करना होगा।

A[i] और A[i+1] के बीच अंतर पर विचार करें। यदि A[i] > A[i+1], तो n > i, चूंकि मान अभी भी कम हो रहे हैं। यदि A[i] <= A[i+1], तो n <= i, क्योंकि मान अब बढ़ रहे हैं। इस मामले में आपको A[i-1] और A[i] के बीच अंतर की जांच करने की आवश्यकता है।

int boundUpper = length(A) - 1; 
int boundLower = 1; 
int i = (boundUpper + boundLower)/2; //initial estimate 

while (true) 
{ 
    if (A[i] > A[i+1]) 
     boundLower = i + 1; 
    else if (A[i-1] >= A[i]) 
     return i; 
    else 
     boundUpper = i; 

    i = (boundLower + boundUpper)/2; 
} 

मैं मामले में आवश्यक त्रुटि जाँच में जोड़ने के लिए है कि A एक तत्व मानदंडों को पूरा नहीं है आप के लिए यह छोड़ देंगे:

यह लॉग समय में एक समाधान है।