目錄

1.題目描述

2.題解

分析

具體實現

方法一（遍歷）：

方法二（排序）：

方法三（二分查找）：

---

1.題目描述

有一個長度為 n 的非降序數組，比如[1,2,3,4,5]，將它進行旋轉，即把一個數組最開始的若干個元素搬到數組的末尾，變成一個旋轉數組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請問，給定這樣一個旋轉數組，求數組中的最小值。

示例

輸入：[3, 4, 5, 1, 2]

返回值：1

2.題解

分析

題目中的數組為

?題目要求我們找出其中的最小值

具體實現

方法一（遍歷）：

尋找數組中的最小值，遍歷數組即可找到最小值

public class Solution {public int minNumberInRotateArray(int[] nums) {if(nums.length == 0){return -1;}int min = nums[0];for (int i = 1; i < nums.length; i++) {if (min > nums[i]) {min = nums[i];}}return min;}
}

?

方法二（排序）：

使用Arrays.sort方法對數組進行降序排序，則nums[0]即為數組的最小值

import java.util.Arrays;public class Solution {public int minNumberInRotateArray (int[] nums) {if(nums.length == 0){return -1;}Arrays.sort(nums);return nums[0];}
}

方法三（二分查找）：

數組原本是一個升序數組，旋轉之后，數組被分成兩部分，前、后半部分分別為升序，后半部分小于前半部分，我們可以利用二分查找的思想，找到其旋轉點，即可找到數組的最小值

首先找到數組首尾兩端元素，并求出數組中間的下標

再將數組中間值與數組首尾兩端元素進行比較，

若nums[mid] > nums[right]，則left = mid + 1

?

?若nums[mid] <?nums[right]，則right = mid

若nums[mid] = nums[right]，?則將right向左移動一位，即right--

?然后進入下一次循環，循環的條件為left < right

通過不斷縮小范圍，最終能夠找到數組的最小值

完整代碼

public class Solution {public int minNumberInRotateArray(int[] nums) {if(nums.length == 0){return -1;}int left = 0;int right = nums.length - 1;while(left < right){//找到數組的中點int mid = (left + right) / 2;if(nums[mid] > nums[right]){//旋轉點在[mid+1, j]中，跳過mid+1左邊元素left = mid + 1;} else if(nums[mid] < nums[right]){//旋轉點在[left, mid]中，跳過mid右邊元素right = mid;}else{//縮小right繼續查找right--;}}//返回旋轉點return nums[left];}
}

?注：題目出自牛客網，鏈接如下

旋轉數組的最小數字_牛客題霸_牛客網 (nowcoder.com)