LeetCode / 5 min read
LeetCode - 153. Find Minimum in Rotated Sorted Array
LeetCode - 153. Find Minimum in Rotated Sorted Array
On this page
題目: 153. Find Minimum in Rotated Sorted Array
假設有一個長度為 n 的陣列，按照升序排序，並且進行了 1 到 n 次旋轉。
例如，陣列 nums = [0,1,2,4,5,6,7] 可能會變成： [4,5,6,7,0,1,2] 如果旋轉了 4 次。 [0,1,2,4,5,6,7] 如果旋轉了 7 次。
注意，將陣列 [a[0], a[1], a[2], ..., a[n-1]] 旋轉 1 次會得到陣列 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
給定已排序且元素唯一的旋轉陣列 nums，請回傳該陣列中的最小元素。
你必須撰寫一個在 O(log n) 時間內運行的演算法。
解題思路
以二元搜尋樹的方式，找出最小值。
Code
Java:
Runtime 0 ms(100%), Memory 42.4 MB(29.4%)
class Solution { public class ValueDuplicateException extends Exception { public ValueDuplicateException(String message) { super(message); } } public int findMin(int[] nums) { int leftFlag = 0; int rightFlag = nums.length - 1; while(leftFlag < rightFlag){ int midFlag = (leftFlag + rightFlag) / 2; // if mid value is greater then right, means min value is in the right side if (nums[midFlag] > nums[rightFlag]){ leftFlag = midFlag + 1; } // if mid value is less then right, means min value is in the left side else if(nums[midFlag] < nums[rightFlag]){ rightFlag = midFlag; } // if mid value equals to right, means it can not happen. // there is no duplicate value. Raise Exception. else{ // throw new ValueDuplicateException("Value is duplicate"); } } return nums[leftFlag]; }}Python3:
Runtime 57 ms(17.66%), Memory 16.7 MB(10.13%)
class Solution: class ValueDuplicateException(Exception): pass def findMin(self, nums: List[int]) -> int: # variant binary search left_flag = 0 right_flag = len(nums) - 1 while left_flag < right_flag: mid_flag = (left_flag + right_flag) // 2 # if mid value is greater then right, means min value is in the right side if nums[mid_flag] > nums[right_flag]: left_flag = mid_flag + 1 # if mid value is less then right, means min value is in the left side elif nums[mid_flag] < nums[right_flag]: right_flag = mid_flag # if mid value equals to right, means it can not happen. # there is no duplicate value. Raise Exception. elif nums[mid_flag] == nums[right_flag]: raise ValueDuplicateException return nums[left_flag]C#:
Runtime 92 ms(33.48%), Memory 38.9 MB(57.81%)
using System;public class Solution { public class ValueDuplicateException : Exception { public ValueDuplicateException(string message) : base(message) { } } public int FindMin(int[] nums) { int leftFlag = 0; int rightFlag = nums.Length - 1; while (leftFlag < rightFlag) { int midFlag = (leftFlag + rightFlag) / 2; if (nums[midFlag] > nums[rightFlag]) { leftFlag = midFlag + 1; } else if (nums[midFlag] < nums[rightFlag]) { rightFlag = midFlag; } else { throw new ValueDuplicateException("Value is duplicate"); } } return nums[leftFlag]; }}Golang:
Runtime 4 ms(56.99%), Memory 2.5 MB(98.74%)
func findMin(nums []int) int { leftFlag := 0 rightFlag := len(nums) - 1 for leftFlag < rightFlag { midFlag := (leftFlag + rightFlag) / 2 if nums[midFlag] > nums[rightFlag] { // if mid value is greater than right, means the minimum value is in the right side leftFlag = midFlag + 1 } else if nums[midFlag] < nums[rightFlag] { // if mid value is less than right, means the minimum value is in the left side rightFlag = midFlag } else if nums[midFlag] == nums[rightFlag] { // if mid value equals right, it means it cannot happen. // There is no duplicate value. Throw an exception. } } return nums[leftFlag]}C++:
Runtime 5 ms(39.12%), Memory 10.1 MB(70.97%)
class Solution {public: int findMin(vector<int>& nums) { int left_flag = 0; int right_flag = nums.size() - 1; while (left_flag < right_flag) { int mid_flag = ( left_flag + right_flag ) / 2; if (nums[mid_flag] > nums[right_flag]){ left_flag = mid_flag + 1; } else if (nums[mid_flag] < nums[right_flag]){ right_flag = mid_flag; } else{ // throw ValueDuplicateException; } } return nums[left_flag]; }};C:
Runtime 3 ms(74.5%), Memory 5.9 MB(92.41%)
int findMin(int* nums, int numsSize){ int leftFlag = 0; int rightFlag = numsSize - 1; while (leftFlag < rightFlag) { int midFlag = (leftFlag + rightFlag) / 2; // if mid value is greater than right, means the minimum value is in the right side if (nums[midFlag] > nums[rightFlag]) { leftFlag = midFlag + 1; } // if mid value is less than right, means the minimum value is in the left side else if (nums[midFlag] < nums[rightFlag]) { rightFlag = midFlag; } // if mid value equals right, it means it cannot happen. // There is no duplicate value. Throw an exception. else if (nums[midFlag] == nums[rightFlag]) { // throw ValueDuplicateException(); } } return nums[leftFlag];}