[LeetCode] 153. Find Minimum in Rotated Sorted Array

轉自LeetCode

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

<Solution>
這題不難，想法如下

• 如果沒有 rotate，就回傳第一個值

• 如過有rotate，從後面往前找，當發現下一個值大於等於目前的值，就回傳目前的值

code如下
c++

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	if(nums.front() > nums.back()) {
	//>> rotated
	for(int i = nums.size() - 1; i >= 1; i--) {
	if(nums[i-1] > nums[i]) {
	return nums[i];
	}
	}
	}
	//>> not rotated
	return nums[0];
	}
	};

view raw findMinInRotatedArray.cpp hosted with ❤ by GitHub

後來題目要求要跑在 O(logN) 的 time complexity

可以使用 binary search 的方式來加速

kotlin

	class Solution {
	fun findMin(nums: IntArray): Int {
	return if (nums.size == 1 || nums.last() > nums.first()) {
	nums[0]
	} else {
	// array is rotated
	var left = 0
	var right = nums.lastIndex
	var mid = 0
	while(left <= right) {
	mid = left + (right - left) / 2
	when {
	nums[mid] > nums[mid+1] -> return nums[mid+1]
	nums[mid-1] > nums[mid] -> return nums[mid]
	nums[mid] > nums.first() -> left = mid + 1
	else -> right = mid -1
	}
	}
	-1
	}
	}
	}

view raw find_minimum_in_rotated_sorted_array.kt hosted with ❤ by GitHub