這篇文章主要介紹“LeetCode題解之怎么實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組的數(shù)字”，在日常操作中，相信很多人在LeetCode題解之怎么實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組的數(shù)字問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”LeetCode題解之怎么實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組的數(shù)字”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)公司是一家朝氣蓬勃的網(wǎng)站建設(shè)公司。公司專注于為企業(yè)提供信息化建設(shè)解決方案。從事網(wǎng)站開(kāi)發(fā)，網(wǎng)站制作，網(wǎng)站設(shè)計(jì)，網(wǎng)站模板，微信公眾號(hào)開(kāi)發(fā)，軟件開(kāi)發(fā)，小程序開(kāi)發(fā)，十載建站對(duì)咖啡廳設(shè)計(jì)等多個(gè)領(lǐng)域，擁有多年的網(wǎng)站制作經(jīng)驗(yàn)。

題目：旋轉(zhuǎn)數(shù)組的最小數(shù)字

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

示例 1：

輸入：[3,4,5,1,2] 輸出：1 示例 2：

輸入：[2,2,2,0,1] 輸出：0

解法一

首先找到題目的提干：

遞增排序數(shù)組(可以重復(fù))，旋轉(zhuǎn)，最小元素

也就是一個(gè)遞增數(shù)組，將一部分移動(dòng)到數(shù)組尾部，比如:

[1,2,3,4,5] //旋轉(zhuǎn)之后 [3,4,5,1,2]

找到其中的最小數(shù)字。

那么我們很容易想到的第一中解法就是遍歷數(shù)組，然后找到某一個(gè)數(shù)字比它前面一個(gè)數(shù)字小的時(shí)候，那么這個(gè)數(shù)字就是我們要找的最小數(shù)字。

因?yàn)檎?lái)說(shuō)都是后面數(shù)字大于前數(shù)字，所以出現(xiàn)小于前數(shù)字，那么就是這個(gè)旋轉(zhuǎn)數(shù)組的分界點(diǎn)，也就是最小數(shù)字了。

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];     } }

方法消耗情況

以后不寫(xiě)這個(gè)了。由于每次測(cè)試用例不同，造成的結(jié)果也相差太大，沒(méi)有參考性。

時(shí)間復(fù)雜度

遍歷一次數(shù)組，所以時(shí)間復(fù)雜度為O(n)

空間復(fù)雜度

沒(méi)有用到另外的空間，所以空間復(fù)雜度為O(1)

解法二

二分法。

有的人可能會(huì)疑惑，二分法不是用來(lái)查找順序數(shù)組的嗎，這個(gè)旋轉(zhuǎn)之后也算嗎?

我們回顧下二分法的關(guān)鍵點(diǎn)就是：

取任意一個(gè)關(guān)鍵數(shù)字，都能通過(guò)判斷 來(lái)確定在我們要的值在哪個(gè)區(qū)間(關(guān)鍵數(shù)字的前后)。

那么在我們的旋轉(zhuǎn)數(shù)組中，能做到這一點(diǎn)嗎?

比如我們?nèi)≈虚g值a和最后值b,如果a大于b，就說(shuō)明這個(gè)分界值在這a和b之間，a之前的數(shù)據(jù)是正確排序的。

如果a小于b，說(shuō)明分界值在a之前，a到b之間的數(shù)據(jù)是正確排序的。

比如剛才的[3,4,5,1,2]，中間值5大于最后的值2，說(shuō)明分界值在5和2之間，也就是1了。

class Solution {     public int minArray(int[] numbers) {         int left=0;         int right=numbers.length-1;         //二分法查找條件         while(left<right){             //找到中間點(diǎn)             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的原因是因?yàn)?，?dāng)numbers[mid]

而numbers[mid]>numbers[right]的情況下，mid不可能為最小，所以設(shè)置為mid+1。

到此，關(guān)于“LeetCode題解之怎么實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組的數(shù)字”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！

網(wǎng)站標(biāo)題：LeetCode題解之怎么實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組的數(shù)字
URL分享：http://chinadenli.net/article28/ihsjjp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、做網(wǎng)站、服務(wù)器托管、網(wǎng)站改版、小程序開(kāi)發(fā)、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)