# LeetCode Hard 154. Find Minimum in Rotated Sorted Array II

tags: leetcode

問題

• Explore
• Problems

アイデア

整列済み配列をある点で回転させた配列の最小の要素を見つけるという問題．要素に重複がないという問題は以前やったことがありますが，今回は重複を認めます．

解法

以下のように分類して同じように解けます．ただし，探索する範囲の左端をleft，右端をright，中央をmidとします．

• mid > right
  • 最小値は$[mid + 1, right]$にある
• left > mid
  • 最小値は$[left + 1, mid]$にある
• left <= mid <= right
  • 最小値は$[left, right - 1]$にある

にある

計算量

配列の長さを$N$とします．

• 時間計算量
  • 平均は$O(\log N)$
  • 最悪は$O(N)$
  • 最悪と成るのは[3, 3, 3, 1, 3]となるような場合
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > nums[right])
        left = mid + 1;
      else if (nums[left] > nums[mid])
        right = mid, left++;
      else  
        right--;
    }
    return nums[left];
  }
};