LeetCode題解之旋轉數組的數字
前言
今天繼續算法題：旋轉數組的最小數字
題目：旋轉數組的最小數字
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為1。
示例 1：
輸入：[3,4,5,1,2] 輸出：1 示例 2：
輸入：[2,2,2,0,1] 輸出：0
解法一
首先找到題目的提干：
遞增排序數組(可以重復)，旋轉，最小元素
也就是一個遞增數組，將一部分移動到數組尾部，比如:
- [1,2,3,4,5]
- //旋轉之后
- [3,4,5,1,2]
找到其中的最小數字。
那么我們很容易想到的第一中解法就是遍歷數組，然后找到某一個數字比它前面一個數字小的時候，那么這個數字就是我們要找的最小數字。
因為正常來說都是后面數字大于前數字，所以出現小于前數字，那么就是這個旋轉數組的分界點，也就是最小數字了。
- class Solution {
- public int minArray(int[] numbers) {
- for(int i=0;i<numbers.length-1;i++){
- if(numbers[i]>numbers[i+1]){
- return numbers[i+1];
- }
- }
- return numbers[0];
- }
- }
方法消耗情況
以后不寫這個了。由于每次測試用例不同，造成的結果也相差太大，沒有參考性。
時間復雜度
遍歷一次數組，所以時間復雜度為O(n)
空間復雜度
沒有用到另外的空間，所以空間復雜度為O(1)
解法二
二分法。
有的人可能會疑惑，二分法不是用來查找順序數組的嗎，這個旋轉之后也算嗎?
我們回顧下二分法的關鍵點就是：
取任意一個關鍵數字，都能通過判斷 來確定在我們要的值在哪個區間(關鍵數字的前后)。
那么在我們的旋轉數組中，能做到這一點嗎?
比如我們取中間值a和最后值b,如果a大于b，就說明這個分界值在這a和b之間，a之前的數據是正確排序的。
如果a小于b，說明分界值在a之前，a到b之間的數據是正確排序的。
比如剛才的[3,4,5,1,2]，中間值5大于最后的值2，說明分界值在5和2之間，也就是1了。
- class Solution {
- public int minArray(int[] numbers) {
- int left=0;
- int right=numbers.length-1;
- //二分法查找條件
- while(left<right){
- //找到中間點
- int mid=left+(right-left)/2;
- if(numbers[mid]<numbers[right]){
- right=mid;
- }else if(numbers[mid]>numbers[right]){
- left=mid+1;
- }else{
- right--;
- }
- }
- return numbers[left];
- }
- }
其中right=mid，left=mid+1的原因是因為，當numbers[mid]
而numbers[mid]>numbers[right]的情況下，mid不可能為最小，所以設置為mid+1。
時間復雜度
二分法最壞情況：
n/(2的x次方)=1，x=long2n。所以時間復雜度為O(longn)
還有一種情況是所有元素全部相同，這種情況下每次都執行right-1，所以時間復雜度為O(n)
空間復雜度
沒有用到另外的空間，所以空間復雜度為O(1)
參考
https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/submissions/
本文轉載自微信公眾號「 碼上積木」，可以通過以下二維碼關注。轉載本文請聯系 碼上積木公眾號。
