資訊專欄INFORMATION COLUMN
摘要：二分迭代法復(fù)雜度時(shí)間空間遞歸?？臻g思路找旋轉(zhuǎn)數(shù)組的起點(diǎn)，實(shí)際上類似找一個(gè)山谷，只要兩邊都比中間高就對(duì)了，這和這題很像。
Find Minimum in Rotated Sorted Array I
二分迭代法 復(fù)雜度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.
You may assume no duplicate exists in the array.
時(shí)間 O(N) 空間 O(N) 遞歸?？臻g
思路4 5 6 7 0 1 2
|
| |
| | |
| | | |
| | | |
| | | | |
| | | | | |
找旋轉(zhuǎn)數(shù)組的起點(diǎn)，實(shí)際上類似找一個(gè)山谷，只要兩邊都比中間高就對(duì)了，這和Find Peak Element這題很像。我們不斷地取中點(diǎn)，找左右兩側(cè)較小的那一側(cè)，直到找到一個(gè)點(diǎn)比左右兩邊都低。
注意在二分到兩頭的時(shí)候要特殊處理一下，返回兩頭和兩頭第二個(gè)中最小的。
代碼public class Solution {
public int findMin(int[] nums) {
for(int min = 0, max = nums.length - 1, mid = max / 2; min <= max; mid = (min + max)/2){
// 如果找到最左邊，返回較小的那個(gè)
if(mid == 0) return Math.min(nums[mid],nums[max]);
// 如果找到最右邊，返回較小的那個(gè)
if(mid == nums.length - 1) return Math.min(nums[mid],nums[min]);
// 如果兩邊都比中間高，返回中間那個(gè)
if(nums[mid] < nums[mid-1] && nums[mid] < nums[mid+1]) return nums[mid];
// 否則，繼續(xù)搜索較小的那一半，找到低谷
if(nums[mid] > nums[max]){
min = mid + 1;
} else {
max = mid - 1;
}
}
return nums[0];
}
}
二分模板
public class Solution {
public int findMin(int[] nums) {
int min = 0, max = nums.length - 1;
while(min <= max){
int mid = min + (max - min) / 2;
if(mid == 0) return Math.min(nums[mid], nums[max]);
if(mid == nums.length - 1) return Math.min(nums[mid], nums[min]);
if(nums[mid + 1] >= nums[mid] && nums[mid - 1] >= nums[mid]){
return nums[mid];
} else if(nums[mid] > nums[max]){
min = mid + 1;
} else {
max = mid - 1;
}
}
return nums[0];
}
}
二分遞歸法
復(fù)雜度
時(shí)間 O(N) 空間 O(N) 遞歸棧空間
思路遞歸法實(shí)現(xiàn)起來更加簡(jiǎn)潔清晰。當(dāng)min等于max時(shí)，我們鎖定了那個(gè)最小值。那如何判斷在哪一半呢，如果num[max] > num[mid]，說明右邊都是有序的，所以那個(gè)旋轉(zhuǎn)點(diǎn)必在左半邊，也就是min到mid之間，如果num[max] < num[mid]，說明右邊有問題，不過mid點(diǎn)本身肯定不是最小值，他已經(jīng)大于num[max]了，所以在mid+1和max之間
注意min == max時(shí)隨便返回一個(gè)
代碼public class Solution {
public int findMin(int[] num) {
return findMin(num, 0, num.length-1);
}
private int findMin(int[] num, int min, int max){
if(min == max){
return num[min];
}
int mid = (min+max)/2;
if(num[max] > num[mid]){
return findMin(num, min, mid);
} else {
return findMin(num, mid+1, max);
}
}
}
Find Minimum in Rotated Sorted Array II
二分遞歸法 復(fù)雜度Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why? 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.
時(shí)間 O(N) 空間 O(N) 遞歸棧空間
思路如果有重復(fù)的話，一旦中間和右邊是相等的，就無法確定是否在左半邊還是右半邊，這時(shí)候我們必須對(duì)兩邊都遞歸求解。如果nums[max]大于等于nums[mid]，則右邊有可能有，如果nums[max]小于等于nums[mid]，則左邊有可能有。
注意要先將左和右的最小值初始化最大整數(shù)，然后求解后，最后返回其中較小的那個(gè)
代碼public class Solution {
public int findMin(int[] nums) {
return findMin(nums, 0, nums.length - 1);
}
public int findMin(int[] nums, int min , int max){
if(min == max){
return nums[min];
}
int mid = (min + max) / 2;
// 先將右邊和左邊可能找到的值都初始化為最大
int right = Integer.MAX_VALUE, left = Integer.MAX_VALUE;
// 找出右邊可能的旋轉(zhuǎn)點(diǎn)
if(nums[mid] >= nums[max]){
right = findMin(nums, mid + 1, max);
}
// 找出左邊可能的旋轉(zhuǎn)點(diǎn)
if (nums[mid] <= nums[max]) {
left = findMin(nums,min, mid);
}
// 返回兩個(gè)中更小的
return Math.min(right,left);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64455.html
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個(gè)，中點(diǎn)值和末位相等。此時(shí)，兩邊同時(shí)遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
摘要：題目要求假設(shè)有一個(gè)升序排序的數(shù)組，在某個(gè)節(jié)點(diǎn)處斷開并調(diào)換了順序。尋找這個(gè)斷開數(shù)組中的最小元素。但是如果我們將頭尾的重復(fù)元素清楚，而只是在數(shù)組中間存在重復(fù)元素的話，如，這樣并不會(huì)影響升序數(shù)組位置的判斷。 題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...
摘要：題目思路個(gè)人覺得這是一道值得回味的二分法題目。與給出的二分法搜索比，這道題目的是未知的，并且是。我個(gè)人是從觀察給出的例子入手的。我本人走的彎路是，過于專注于，從而邏輯變得復(fù)雜。其實(shí)，，和步就可以幫助我們順利找到最小值。 題目 http://www.lintcode.com/en/pr... Suppose a sorted array is rotated at some pivot ...
摘要：難度就是說一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。比如全部是的數(shù)列，和除了某位置有個(gè)，其余全部是的數(shù)列，都是合法的。在這里，測(cè)試用例也進(jìn)行了增加，盡量覆蓋各種奇葩情況。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...
摘要：難度就是說一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。數(shù)組無重復(fù)值無重復(fù)的話就比較簡(jiǎn)單，用二分查找即可。當(dāng)前游標(biāo)始終是左右游標(biāo)中點(diǎn)位置，與左右游標(biāo)的數(shù)值比較。解法有幾個(gè)要點(diǎn)基本終止條件為左邊的數(shù)比當(dāng)前的數(shù)大，那么當(dāng)前數(shù)即是最小值。 Question:Suppose a sorted array is rotated at some pivot unknown to you b...
閱讀 3698·2021-09-07 10:19
閱讀 3639·2021-09-03 10:42
閱讀 3592·2021-09-03 10:28
閱讀 2560·2019-08-29 14:11
閱讀 819·2019-08-29 13:54
閱讀 1605·2019-08-29 12:14
閱讀 426·2019-08-26 12:12
閱讀 3624·2019-08-26 10:45
