หาค่าน้อยสุดในอาเรย์หมุนแบบมีซ้ำใน C++ (Find Minimum in Rotated Sorted Array II)

ภาพรวมปัญหา

อาเรย์เรียงแล้วหมุน (rotated) อาจมีค่าซ้ำ หาค่าน้อยสุด

ตัวอย่าง

[4,5,5,5,6,8,2,3,4] → 2

วิธีแก้ปัญหา: Binary Search แบบจัดการค่าซ้ำ

แบ่งกรณีจาก mid:
- arr[low] < arr[mid]: ด้านซ้ายเรียง → min อยู่ขวา หรือ arr[low]
- arr[high] > arr[mid]: ด้านขวาเรียง → min อยู่ซ้าย หรือ arr[mid]
- arr[low] == arr[mid]: ไม่แน่ใจ → low++
- arr[high] == arr[mid]: ไม่แน่ใจ → high--

โค้ด C++ (Recursive)

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

class Solution {
public:
    int search(vector<int>& arr, int low, int high) {
        if (low == high) return arr[low];
        int mid = low + (high - low) / 2;
        int ans = INT_MAX;
        if (arr[low] < arr[mid]) ans = min(arr[low], search(arr, mid, high));
        else if (arr[high] > arr[mid]) ans = min(arr[mid], search(arr, low, mid));
        else if (arr[low] == arr[mid]) ans = min(arr[low], search(arr, low+1, high));
        else if (arr[high] == arr[mid]) ans = min(arr[high], search(arr, low, high-1));
        return ans;
    }
    int findMin(vector<int>& nums) {
        return search(nums, 0, nums.size()-1);
    }
};

int main() {
    Solution ob;
    vector<int> v = {4,5,5,5,6,8,2,3,4};
    cout << (ob.findMin(v));
}

ผลลัพธ์

2

การวิเคราะห์ความซับซ้อน

• เวลา: O(log n) เฉลี่ย, O(n) สูงสุด (กรณีซ้ำมาก)
• พื้นที่: O(log n) recursion stack