來自:碼農(nóng)田小齊
算法將是我今后更新的重點,因為我個人非常喜歡。。而且面試考它?。∮腥苏f刷題沒有用,但是你做了題就能感受到 coding 能力的提升和對語言熟悉度的提升。新的一年,每日一題,我們一起進步一起NB!
今天第一題選了我最喜歡的也是折磨了我很久的但并不算難的題目,最終是因為在 GS 電面中被問到了,我才痛下決心把這類題目一網(wǎng)打盡。
先來看最基本版的題目:Leetcode 153題
題干是給了一個【本來排好序了的 且為升序】的數(shù)組,然后又在某個不知道的位置旋轉(zhuǎn)了一下,所謂旋轉(zhuǎn),就是把前面那堆數(shù)移到后面來了,求新數(shù)組的最小值。比如:
原 array:[0, 1, 2, 4, 5, 6, 7]
rotate 之后就是:[4, 5, 6, 7, 0, 1, 2]
輸出:最小值 0
解法一:
Brute Force 暴力解法就是每個數(shù)都過一遍,然后用一個變量記錄我們見到過的最小值并隨時更新。(這個應該都會吧,不會的話可以后臺留言告訴我。。請讓我看到你。。)
Time complexity = O(n),因為每個數(shù)都過了一遍;
Space complexity = O(1),因為只用了有限幾個變量。
解法二:
在 O(n) 的基礎上我們還想優(yōu)化,那方向是 O(logn),再想想查找類算法的很容易想到了 binary search。
binary search 的做法就是每輪排除一半,留下另一半是包含正確答案的,再不斷縮小范圍,把答案找出來。那么解決的關鍵就在于如何殺掉這一半而不能把答案誤殺了。中文叫二分查找,我認為翻譯的挺好的,因為只有一次分兩份,去掉一份,才能保證時間復雜度是 O(logn)。(此處不懂可以后臺留言給我,我會根據(jù)反饋在之后的文章補充。)
那么二分查找題目的考點就在于如何排除掉這一半了,一般是通過比較中間的數(shù)和左右兩端或者目標值的關系,但沒有統(tǒng)一的規(guī)律,否則還考啥?只能多見多去領悟其精髓,我會在更新完所有 binary search 的題目之后做個總結(jié)。
就這一題來說,我們比較 array[mid] 和 array[left] or array[right] 的大小關系,哪邊都行。
方法一、先看和右邊的比較
-
如果 array[mid] > array[right],如下圖例子,7 比 2 要大,這是不正常的(不升序)的,說明最小值在右邊,所以排除左邊以及 mid(array[mid] 已經(jīng)比 array[right] 大了,不可能為最小值),所以 -
left = mid + 1;
-
如果 array[mid] < array[right](沒有=,因為沒有duplicates),說明右邊是 sorted 的,說明 最小值在左邊甚至可能就是 mid 本身,所以 -
所以 right = mid。
-
while終止條件是 left == right 的時候,此時 mid = left = right, 返回nums[left] = nums[right] 都行。
// Java
class Solution{
public int findMid(int[] nums) {
if(nums == null || nums.length == 0) {
return -1; // discuss with interviewer
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left)/2;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}
/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.
Memory Usage: 38.5 MB, less than 79.54% of Java online submissions for Find Minimum in Rotated Sorted Array.
*/
方法二、再看和左邊比較
-
如果 array[mid] >= array[left](這里可能=,因為 mid 可能就是 left;而 mid 不可能是 right,因為 Java 向0取整且如果 left = right 就跳出循環(huán)了),那么 左邊是 sorted 的,最小值在右邊(題目說一定 rotated 了),所以 left = mid + 1,但有兩點要注意: 注意 ? : 最小值有可能就是 left,雖然最初數(shù)組是 rotate 了,但是在減半之后有可能就是完整 sorted 的 所以此方法還要加一步:最開始先判斷是否是sorted的,即array[left] vs array[right]
-
如果 array[mid] < array[left],那么右邊是 sorted 的,最小值在左邊甚至是 mid 本身,所以 right = mid。 -
while loop 條件同上
// Java
class Solution {
public int findMid(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
if(nums[left] < nums[right]) { //?
return nums[left];
}
int mid = left + (right - left)/2;
if(nums[mid] >= nums[left]) { //?
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}
/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.
Memory Usage: 38.6 MB, less than 77.27% of Java online submissions for Find Minimum in Rotated Sorted Array.
*/
這題說完了。
Follow up 是154題,可能有 duplicates 的情況。大家可以稍作思考再往下看。
基本思路和上一題一樣,但是 [3, 3, 1, 3] 不work,因為當 mid = right 時,無法判斷最小值到底在哪邊,所以只能一步步走,worst case O(n) 避免不了。
// Java
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left)/2;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] == nums[right]) {
right --;
} else {
right = mid;
}
}
return nums[left];
}
}
/*
Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array II.
Memory Usage: 41.8 MB, less than 6.25% of Java online submissions for Find Minimum in Rotated Sorted Array II.
*/
以上就是 rotate array 中找最小值的完整方法了,明天我們來看在 rotate array 中找一個特定目標值的題目,這題有很多方法,我會分享我認為覺得最好的一種,會對 binary search 的理解更加深刻。
題目:Leetcode 33 & 81
特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容,還沒關注的小伙伴,可以長按關注一下:
長按訂閱更多精彩▼
如有收獲,點個在看,誠摯感謝
免責聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!