C++ . में सर्कुलर ऐरे लूप

मान लीजिए कि हमारे पास सकारात्मक और नकारात्मक पूर्णांक मानों की एक गोलाकार सरणी संख्या है। यदि सूचकांक में कोई संख्या k एक धनात्मक संख्या है, तो k चरणों को आगे बढ़ाएँ। अन्यथा, यदि यह ऋणात्मक (-k) है, तो k कदम पीछे ले जाएँ। चूंकि सरणी गोलाकार है, हम मान सकते हैं कि अंतिम तत्व का अगला तत्व पहला तत्व है, और पहले तत्व का पिछला तत्व अंतिम तत्व है। हमें यह जांचना है कि अंकों में लूप (या चक्र) है या नहीं। एक चक्र एक ही सूचकांक और चक्र की लंबाई> 1 पर शुरू और समाप्त होना चाहिए। इसलिए यदि इनपुट [2,-1,1,2,2] जैसा है, तो आउटपुट सत्य होगा, क्योंकि सूचकांक से एक चक्र है 0 -> 2 -> 3 -> 0 की लंबाई 3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=अंकों का आकार

  
  

• यदि n <2 है, तो झूठी वापसी करें

  
  

• मैं के लिए 0 से n -1 की सीमा में, अंक [i]:=अंक [i] मॉड n

• मेरे लिए 0 से n - 1 की सीमा में

  • अगर nums[i] =0, तो अगले पुनरावृत्ति के लिए जारी रखें;

  • धीमा =मैं, तेज़ =मैं;

  • जबकि अंक [धीमा] * अंक [तेज़]> 0 और अंक [तेज़ के अगले] * अंक [धीमे]> 0

    • धीमा =धीमा के आगे

    • उपवास :=अगले उपवास के बाद

    • अगर धीमा =तेज, तो

      • अगर धीमा =धीमा के बाद, फिर लूप से बाहर आएं

      • सही लौटें

  • एक्स:=अंक [i]

  • धीमा :=मैं

  • जबकि अंक [धीमा] * x> 0

    • अस्थायी :=धीमी गति के बाद

    • धीमी गति के आगे :=0

    • धीमा:=अस्थायी

• झूठी वापसी

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int next(vector<int>& nums, int i){
      int n = nums.size();
      return (n+nums[i]+i)%n;
   }
   bool circularArrayLoop(vector<int>& nums) {
      int n = nums.size();
      if(n < 2) return false;
      for(int i = 0; i < n; i++)nums[i] %= n;
      for(int i = 0; i < n; i++){
         if(nums[i] == 0) continue;
         int slow = i;
         int fast = i;
         while(nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0){
            slow = next(nums, slow);
            fast = next(nums, next(nums, fast));
            if(slow == fast){
               if(slow == next(nums, slow))
               break;
               return true;
            }
         }
         int x = nums[i];
         slow = i;
         while(nums[slow] * x > 0){
            int temp = next(nums, slow);
            nums[slow] = 0;
            slow = temp;
         }
      }
      return false;
   }
};
main(){
   vector<int> v = {2,-1,1,2,2};
   Solution ob;
   cout << (ob.circularArrayLoop(v));
}

इनपुट

[2,-1,1,2,2]

आउटपुट

1