回転ソートされた配列の中で最小の値を見つける II

回転後の配列は、最小値の右側の要素はすべて最小値以上であり、最小値の左側の要素はすべて最小値以上であるという特性を満たします。

そのため、それぞれの二分法を現在の区間の左端または右端と比較することで、最小値がどこにあるかを判断することができます。

ここでは、区間の中点 nums[mid]の値が、区間の右端 nums[right]と1つずつ比較されます。

1. nums[mid] < nums[right]の場合、これは区間の右半分が昇順であることを意味するので、最小値はこの部分にあってはならず、最小値はせいぜい nums[mid]にしかならないので、right = mid; とします。

2. nums[mid] < nums[right]の場合、これは区間の右半分が昇順ではないことを意味し、配列の回転が右半分にあることを示します。

3. nums[mid] == nums[right]の場合、配列がすべて同じ要素である場合と、midとrightの間で上がってから下がる場合、後者のmidとrightの間で下がってから上がる場合があります。 いずれにせよ、区間内の要素を探し続ける必要がありますが、今度は半分にすることはできず、right -> right -> right = 1、つまり重複する要素を削除して、nums[mid]とnums[right]のサイズ関係を決定し続けるしかありません。= 1、つまり重複する要素を取り除き、nums[mid]とnums[right]のサイズの関係を決定し続けます。

第3のケースは、最悪の場合、一度に1つの要素しか削除できないので、この問題の最悪の場合の時間複雑度はO(n)です。

コードは以下の通り：

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