पायथन में जांचें कि कोई ऐरे सॉर्टेड और रोटेटेड है या नहीं

मान लीजिए हमारे पास n अद्वितीय मानों का एक ऐरे है। हमें यह जांचना है कि क्या यह ऐरे सॉर्टेड और एंटी-क्लॉकवाइज रोटेटेड है। यहां कम से कम एक रोटेशन आवश्यक है, इसलिए पूरी तरह से सॉर्टेड ऐरे को सॉर्टेड और रोटेटेड नहीं माना जाता।

उदाहरण के लिए, यदि इनपुट nums = [4,5,6,8,1,3] है, तो आउटपुट True होगा क्योंकि हम इसे दो बार क्लॉकवाइज दिशा में रोटेट करके सॉर्टेड [1, 3, 4, 5, 6, 8] प्राप्त कर सकते हैं।

समाधान दृष्टिकोण

एक सॉर्टेड और रोटेटेड ऐरे में न्यूनतम तत्व "पिवट" होता है। इसके दोनों ओर के उप-सरणी सॉर्टेड होने चाहिए, और अंतिम तत्व पहले तत्व से छोटा होना चाहिए।

एल्गोरिदम चरण:

न्यूनतम तत्व और उसका इंडेक्स ढूंढें
न्यूनतम इंडेक्स से पहले के भाग की जांच करें कि वह सॉर्टेड है या नहीं
न्यूनतम इंडेक्स के बाद के भाग की जांच करें कि वह सॉर्टेड है या नहीं
यदि दोनों भाग सॉर्टेड हैं और nums[-1] < nums[0], तो True लौटाएं
अन्यथा False लौटाएं

पायथन कार्यान्वयन

def solve(nums):
    min_element = min(nums)
    min_index = nums.index(min_element)
    
    # न्यूनतम से पहले का भाग जांचें
    before_sorted = True
    for i in range(1, min_index):
        if nums[i] < nums[i-1]:
            before_sorted = False
            break
    
    # न्यूनतम के बाद का भाग जांचें
    after_sorted = True
    for i in range(min_index + 1, len(nums)):
        if nums[i] < nums[i-1]:
            after_sorted = False
            break
    
    if before_sorted and after_sorted and nums[-1] < nums[0]:
        return True
    return False

nums = [4, 5, 6, 8, 1, 3]
print(solve(nums))  # True

इनपुट

[4,5,6,8,1,3]

आउटपुट

True

व्याख्या:

ऐरे [4,5,6,8,1,3] में न्यूनतम तत्व 1 इंडेक्स 4 पर है।

इससे पहले: [4,5,6,8] - सॉर्टेड ✓
इसके बाद: [3] - सॉर्टेड ✓
अंतिम तत्व (3) < पहला तत्व (4) ✓

इसलिए यह सॉर्टेड और रोटेटेड ऐरे है।