[LeetCode][Medium] 153. Find Minimum in Rotated Sorted Array

Leetcode 網址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

題目說明:

給一個長度為 n 的已排序並 rotate 過 1 ~ n  次的陣列，請找出這個陣列中最小的數值。

Rotate 範例: 

原始已排序陣列: [0,1,2,4,5,6,7]

經過 1 次 rotate => [7,0,1,2,3,4,5,6]

經過 2 次 rotate => [6,7,0,1,2,3,4,5]

經過 3 次 rotate => [5,6,7,0,1,2,3,4]

...

經過 7 次 rotate => [0,1,2,3,4,5,6,7]

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

解題說明:

觀察範例可以發現， 

rotate  1 次代表第 1 ~ 1 個元素會為第 n 大到第 n 大，第 2 個元素為最小

rotate  2 次代表第 1 ~ 2 個元素會為第 n - 1 大到第 n 大，第 3 個元素為最小

rotate  3 次代表第 1 ~ 3 個元素會為第 n - 2 大到第 n 大，第 4 個元素為最小

...

rotate  n 次代表第 1 ~ n 個元素會為第 1 大到第 n 大，第 n 個元素為最小

以此邏輯即可以寫出非常簡單的算法囉 ~

程式碼

class Solution {
public:
    int findMin(vector<int>& nums) {
        for (int i = 0, maxNum = INT_MIN; i < nums.size(); i++) {            
        	if (nums[i] >= maxNum) maxNum = nums[i];
        	else return nums[i];
        }
        return nums[0];
    }
};




結果

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Find Minimum in Rotated Sorted Array.

Memory Usage: 10.1 MB, less than 98.02% of C++ online submissions for Find Minimum in Rotated Sorted Array.