【問題描述】[簡單]

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 示例 1：輸入：[3,4,5,1,2] 輸出：1 示例 2：輸入：[2,2,2,0,1] 輸出：0

【解答思路】

1. 函數(shù)法

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public int minArray(int[] numbers) {Arrays.sort(numbers);return numbers[0];}

2. 二分法

時間復(fù)雜度：O(logN) 空間復(fù)雜度：O(1)

class Solution {public int minArray(int[] numbers) {int i = 0, j = numbers.length - 1;while (i < j) {int m = (i + j) / 2;if (numbers[m] > numbers[j]) i = m + 1;else if (numbers[m] < numbers[j]) j = m;else j--;}return numbers[i];} }

3. 分治

二分的減治思想本來就是分治思想的特殊情況

時間復(fù)雜度：O(logN) 空間復(fù)雜度：O(1)

public class Solution {public int minArray(int[] numbers) {int len = numbers.length;if (len == 0) {return 0;}return minArray(numbers, 0, len - 1);}/*** 在子區(qū)間 [left, right] 里查找最小值** @param numbers* @param left* @param right* @return*/private int minArray(int[] numbers, int left, int right) {if (left == right) {return numbers[left];}int mid = (left + right) >>> 1;if (numbers[mid] > numbers[right]) {return minArray(numbers, mid + 1, right);} else if (numbers[mid] == numbers[right]) {return minArray(numbers, left, right - 1);} else {return minArray(numbers, left, mid);}} }

【總結(jié)】

1.Arrays.sort()

1.1.Arrays.sort(int[] a)

1.2.Arrays.sort(int[] a , int fromIndex, int toIndex)

2. 二分法

中間 和兩邊對比 使用排除發(fā)減少范圍

3. 二分的減治思想本來就是分治思想的特殊情況

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/

參考鏈接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/er-fen-jian-zhi-si-xiang-fen-zhi-si-xiang-by-liwei/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[11]题[旋转数组的最小数字][二分法][分治]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。