ตรวจสอบ Array Sorted และ Rotated ใน C++

โจทย์

กำหนด Array ตรวจสอบว่าเป็น Sorted (Non-decreasing) และ Rotated หรือไม่ กล่าวคือ มี Pivot จุดเดียวที่ Array "วนกลับ" (เช่น [3,4,5,1,2] = Sorted [1,2,3,4,5] Rotated ที่ Index 3)

ตัวอย่าง

[7, 8, 9, 4, 5, 6] → True (Sorted [4,5,6,7,8,9] Rotated)

[1, 5, 7, 6, 2, 3] → False (Not sorted)

[1, 2, 3, 4, 5] → True (Sorted, Rotated 0 positions)

แนวคิด: นับ "Drop Points"

ใน Sorted & Rotated Array จะมีจุดที่ arr[i] > arr[i+1] อยู่ สูงสุด 1 จุด (รวมจุดวนรอบ arr[n-1] > arr[0])

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool checkSortedAndRotated(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return true;
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[(i + 1) % n]) {
            count++;
        }
    }
    return count <= 1;
}

// Alternative: Find Pivot + Verify
bool checkSortedAndRotatedV2(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return true;
    
    int pivot = -1;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            if (pivot != -1) return false; // More than 1 drop
            pivot = i;
        }
    }
    
    // Check wrap-around
    if (arr[n - 1] > arr[0]) {
        if (pivot != -1) return false;
        pivot = n - 1;
    }
    
    // If no pivot, it's sorted (rotated 0)
    if (pivot == -1) return true;
    
    // Verify both parts sorted
    for (int i = 0; i < pivot; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    for (int i = pivot + 1; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

int main() {
    vector<vector<int>> tests = {
        {7, 8, 9, 4, 5, 6},   // True
        {1, 5, 7, 6, 2, 3},   // False
        {1, 2, 3, 4, 5},      // True (rotated 0)
        {5, 6, 7, 1, 2, 3, 4}, // True
        {2, 1},                // True
        {1, 1, 1},             // True (duplicates allowed)
        {3, 3, 1, 2},          // True
        {3, 4, 5, 1, 2, 2},    // True
    };
    
    for (auto& t : tests) {
        cout << (checkSortedAndRotated(t) ? "True" : "False") << " ";
        for (int x : t) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

Complexity

• Time: O(n) - Single Pass
• Space: O(1)

ข้อควรระวัง: Duplicates

ถ้า Allow Duplicates (Non-decreasing) → [1,1,1] เป็น True, [2,1,2,2] เป็น True

ถ้า Strict Increasing → ต้องแก้เงื่อนไขเป็น arr[i] >= arr[i+1]

ผลลัพธ์

True 7 8 9 4 5 6
False 1 5 7 6 2 3
True 1 2 3 4 5
True 5 6 7 1 2 3 4
True 2 1
True 1 1 1
True 3 3 1 2
True 3 4 5 1 2 2

สรุป

Check Sorted & Rotated = นับจุดที่ arr[i] > arr[(i+1)%n] ≤ 1 จุด O(n) Time O(1) Space - LeetCode 1752 (Check if Array Is Sorted and Rotated)