資訊專欄INFORMATION COLUMN
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個，中點(diǎn)值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說明已夾逼得到最小值。
Find Minimum in Rotated Sorted Array Problem
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
NoticeYou may assume no duplicate exists in the array.
ExampleGiven [4, 5, 6, 7, 0, 1, 2] return 0
Note排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。我們先來看看rotated sorted array有哪些情況，再確定如何使用二分法：
//LO M HI
// 789123456
// 678912345
// 456789123
// 123456789
上面的例子分別是較小元素，最小元素，較大元素，中位數(shù)在中點(diǎn)的情況?？梢?，用隊(duì)首元素num[start]和中點(diǎn)num[mid]比較沒有意義。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。
Solutionpublic class Solution {
public int findMin(int[] num) {
int start = 0, end = num.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[end] > num[mid]) end = mid;
else start = mid;
}
return num[start] < num[end] ? num[start] : num[end];
}
}
Find Minimum in Rotated Sorted Array
Problem
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
ExampleGiven [4,4,5,6,7,0,1,2] return 0
Note53335 x 33533 x 55535 x 42333 x 45333 x
上面這些case是很難直接用二分法判斷的，只能對中點(diǎn)兩邊同時使用二分法遞歸，或者完全遍歷數(shù)組求最優(yōu)解。
二分法遞歸的步驟是：建立helper()函數(shù)，當(dāng)中點(diǎn)值大于等于末位值，夾逼到后半段，舍棄中間值；當(dāng)中點(diǎn)值小于等于末位值，夾逼到前半段，不舍棄中間值。這里有一種情況是（上述后三個case），中點(diǎn)值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說明已夾逼得到最小值。
二分法遞歸
public class Solution {
public int findMin(int[] num) {
return helper(num, 0, num.length-1);
}
public int helper(int[] num, int start, int end) {
if (start == end) return num[start];
int mid = start + (end - start) / 2;
int left = Integer.MAX_VALUE, right = left;
if (num[mid] >= num[end]) {
right = helper(num, mid+1, end);
}
if (num[mid] <= num[end]) {
left = helper(num, start, mid);
}
return Math.min(left, right);
}
}
暴力循環(huán)
public class Solution {
public int findMin(int[] num) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < num.length; i++) {
min = Math.min(num[i], min);
}
return min;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65697.html
摘要：找中點(diǎn)若起點(diǎn)小于中點(diǎn)，說明左半段沒有旋轉(zhuǎn)，否則說明右半段沒有旋轉(zhuǎn)。在左右半段分別進(jìn)行二分法的操作。只判斷有無，就容易了。還是用二分法優(yōu)化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...
摘要：二分迭代法復(fù)雜度時間空間遞歸?？臻g思路找旋轉(zhuǎn)數(shù)組的起點(diǎn)，實(shí)際上類似找一個山谷，只要兩邊都比中間高就對了，這和這題很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...
摘要：題目思路個人覺得這是一道值得回味的二分法題目。與給出的二分法搜索比，這道題目的是未知的，并且是。我個人是從觀察給出的例子入手的。我本人走的彎路是，過于專注于，從而邏輯變得復(fù)雜。其實(shí)，，和步就可以幫助我們順利找到最小值。 題目 http://www.lintcode.com/en/pr... Suppose a sorted array is rotated at some pivot ...
摘要：題目要求假設(shè)有一個升序排序的數(shù)組，在某個節(jié)點(diǎn)處斷開并調(diào)換了順序。尋找這個斷開數(shù)組中的最小元素。但是如果我們將頭尾的重復(fù)元素清楚，而只是在數(shù)組中間存在重復(fù)元素的話，如，這樣并不會影響升序數(shù)組位置的判斷。 題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...
Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...
閱讀 2958·2021-11-23 09:51
閱讀 1675·2021-10-15 09:39
閱讀 1068·2021-08-03 14:03
閱讀 2897·2019-08-30 15:53
閱讀 3445·2019-08-30 15:52
閱讀 2494·2019-08-29 16:17
閱讀 2801·2019-08-29 16:12
閱讀 1657·2019-08-29 15:26
