【leetcode刷題】31.旋轉數組的最小數字——Java版

一條coding 2021-08-15 16:31:57 阅读数:406

本文一共[544]字,预计阅读时长:1分钟~
leetcode 最小 java

歡迎訂閱《leetcode》專欄,每日一題,每天進步

什麼鬼題目呀,管你旋不旋轉,直接輸出最小值不就完了。。。

——leetcode此題熱評

前言

哈嘍,大家好,我是一條。

糊塗算法,難得糊塗

考慮再三,也問了大佬,决定還是繼續强化簡單題。

Question

劍指 Offer 11. 旋轉數組的最小數字

難度:簡單

把一個數組最開始的若幹個元素搬到數組的末尾,我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉,輸出旋轉數組的最小元素。例如,數組 [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

Solution

此題的錶述比較繞,很多人一遍可能看不懂。其實就像評論說的,最小值就可以了,和旋轉沒關系。

但為了不超時,應該考慮更快的方法。

旋轉數組:所謂旋轉數組,有這麼幾個點:

  • 一個昇序排列的數組
  • 將前面的一段截下來放到後面
  • 數組可以分成左排序,右排序,旋轉點幾個部分
  • 左排序都大於右排序
  • 旋轉點就是我們要找的最小值

二分查找:

所以問題由最小值問題轉換為查找旋轉點問題,最快的辦法就是二分查找。

  • 數組中最特殊的比特置是左邊比特置 left 和右邊比特置 right,將它們與中間比特置 mid 的值進行比較,進而判斷最小數字出現在哪裏。
  • 注意:不能用左邊與中間比較,舉例:[3, 4, 5, 1, 2][1, 2, 3, 4, 5]
  • 如果右邊大於中間:說明在左邊,將右端點收縮
  • 如果右邊小於中間:說明在右邊,將左端點收縮

Code

所有leetcode代碼已同步至github

歡迎star

/** * @author yitiaoIT */
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];
}
}

Result

複雜度分析

  • 時間複雜度:O(logn)

尋寶

今天是堅持刷題更文的第31/100天

各比特的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

更多算法題歡迎關注專欄《leetcode》

為了回饋各比特粉絲,禮尚往來,給大家准備了一條多年積累下來的優質資源,包括 學習視頻、面試資料、珍藏電子書等

大家可以先自己找一下獲取方式,尋寶遊戲現在開始。

如果實在找不到可以評論區留言或私信我領取,不過一定要先關注哦!不然無法發私信!

版权声明:本文为[一條coding]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815163128762v.html