วงกลมอาร์เรย์ใน C ++

สมมติว่าเรามีจำนวนอาร์เรย์วงกลมของค่าจำนวนเต็มบวกและลบ หากตัวเลข k ที่ดัชนีเป็นจำนวนบวก ให้ก้าวไปข้างหน้า k ขั้น มิฉะนั้น หากเป็นค่าลบ (-k) ให้เลื่อนถอยหลัง k ขั้น เนื่องจากอาร์เรย์เป็นวงกลม เราสามารถสรุปได้ว่าองค์ประกอบถัดไปขององค์ประกอบสุดท้ายคือองค์ประกอบแรก และองค์ประกอบก่อนหน้าขององค์ประกอบแรกคือองค์ประกอบสุดท้าย เราต้องตรวจสอบว่ามีการวนซ้ำ (หรือรอบ) ใน nums หรือไม่ รอบจะต้องเริ่มต้นและสิ้นสุดที่ดัชนีเดียวกันและความยาวของวงจร> 1 ดังนั้นหากอินพุตเป็นเช่น [2,-1,1,2,2] ผลลัพธ์จะเป็นจริงเนื่องจากมีวงจรจากดัชนี 0 -> 2 -> 3 -> 0 ของความยาว 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums

  
  

• ถ้า n <2 ให้คืนค่าเท็จ

  
  

• สำหรับฉันในช่วง 0 ถึง n - 1, nums[i] :=nums[i] mod n

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า nums[i] =0 ให้ทำซ้ำต่อไป

  • ช้า =ฉัน, เร็ว =ฉัน;

  • ในขณะที่ nums[slow] * nums[fast]> 0 และ nums[next of fast] * nums[slow]> 0

    • ช้า =ถัดจากช้า

    • เร็ว :=ถัดไปของเร็ว

    • ถ้าช้า =เร็ว แล้ว

      • ถ้าช้า =ถัดไปของช้า ก็ออกมาจากลูป

      • คืนความจริง

  • x :=nums[i]

  • ช้า :=ฉัน

  • ในขณะที่ nums[ช้า] * x> 0

    • temp :=ถัดไปของช้า

    • ช้าต่อไป :=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