Find Minimum in Rotated Sorted Array II (H)
題目
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.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?
題意
將一遞增數列的隨機后半部分與前半部分換位，得到新陣列，在新陣列中查找最小值(陣列中有重復的值)，
思路
與 0153. Find Minimum in Rotated Sorted Array 相比，允許陣列中存在重復的值，這帶來的問題是，很難根據一個元素與最左側元素的大小關系來判斷它是落在左區間還是右區間，如陣列 [10, 10, 1, 10, 10, 10]，
因此在 0153. Find Minimum in Rotated Sorted Array 解法的基礎上做出改動：只有當nums[mid]與nums[left]存在嚴格的大于小于關系時，才能確定mid是落在左區間還是右區間，而當nums[mid]等于nums[left]時，因為無法有效判斷區間歸屬，只能令left右移(或者right左移)，在最壞情況下(全元素一樣)，時間復雜度退化至\(O(N)\)，
也可以用分治法實作，
代碼實作
Java
二分法
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
// 當前區間已經是有序區間，則最小值就是nums[left]
if (nums[left] < nums[right]) {
return nums[left];
}
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right--;
}
}
return nums[right];
}
}
分治法
class Solution {
public int findMin(int[] nums) {
return findMin(nums, 0, nums.length - 1);
}
private int findMin(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
return Math.min(findMin(nums, left, mid), findMin(nums, mid + 1, right));
}
}
JavaScript
二分法
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function (nums) {
let left = 0, right = nums.length - 1
while (left < right) {
if (nums[left] < nums[right]) {
return nums[left]
}
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] < nums[left]) {
right = mid
} else if (nums[mid] > nums[left]) {
left = mid + 1
} else {
left++
}
}
return nums[left]
}
分治法
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function (nums) {
return dac(nums, 0, nums.length - 1)
}
let dac = function (nums, left, right) {
if (left === right) {
return nums[left]
}
let mid = Math.trunc((right - left) / 2) + left
return Math.min(dac(nums, left, mid), dac(nums, mid + 1, right))
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14519.html
標籤：其他
上一篇：【演算法】排序01——從分治演算法的角度理解快速排序（含代碼實作）
下一篇：包含min函式的堆疊