資訊專欄INFORMATION COLUMN
摘要：找中點若起點小于中點，說明左半段沒有旋轉(zhuǎn)，否則說明右半段沒有旋轉(zhuǎ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 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
ExampleFor [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1.
ChallengeO(logN) time
Note找中點：若起點小于中點，說明左半段沒有旋轉(zhuǎn)，否則說明右半段沒有旋轉(zhuǎn)。
在左右半段分別進行二分法的操作。
public class Solution {
public int search(int[] A, int target) {
int start = 0, end = A.length-1, mid = 0;
while (start <= end) {
mid = (start+end)/2;
if (A[mid] == target) return mid;
if (A[start] <= A[mid]) {
if (A[start] <= target && target <= A[mid]) end = mid-1;
else start = mid+1;
}
else {
if (A[mid] < target && target <= A[end]) start = mid+1;
else end = mid-1;
}
}
return -1;
}
}
Search in Rotated Sorted Array II
Problem
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
Note只判斷有無，就容易了。
Solution還是用二分法優(yōu)化
public class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) return false;
int start = 0, end = nums.length-1;
while (start <= end) {
int mid = start+(end-start)/2;
if (nums[mid] == target || nums[start] == target || nums[end] == target) return true;
if (nums[start] < nums[mid]) {
if (nums[start] <= target && target < nums[mid]) end = mid-1;
else start = mid+1;
}
else if (nums[start] > nums[mid]) {
if (nums[mid] < target && target <= nums[end]) start = mid+1;
else end = mid-1;
}
else {
if (nums[start] != target) start++;
if (nums[end] != target) end--;
}
}
return false;
}
}
Updated 2018-08
class Solution {
public boolean search(int[] nums, int target) {
int start = 0, mid = 0, end = nums.length-1;
while (start <= end) {
mid = start+(end-start)/2;
if (nums[mid] == target || nums[start] == target || nums[end] == target) return true;
if (nums[start] < nums[mid]) {
if (nums[start] < target && target < nums[mid]) end = mid-1;
else start = mid+1;
} else if (nums[start] > nums[mid]) {
if (nums[mid] < target && target < nums[end]) start = mid+1;
else end = mid-1;
} else {
start++;
end--;
}
}
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65939.html
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點和中點元素的大小關(guān)系即可。這里有一種情況是上述后三個，中點值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
摘要：如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉(zhuǎn)點，導(dǎo)致了不再有序。因為只有一個旋轉(zhuǎn)點，所以一分為二后，肯定有一半是有序的。 Search 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 7 mi...
摘要：這里相比于思路一，更適用于目標(biāo)節(jié)點在中間的情況，而思路一在目標(biāo)節(jié)點分布在數(shù)組兩側(cè)會效率更高。 題目要求 Suppose an array sorted in ascending order 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 ...
摘要：如正常的升序排列應(yīng)該是，，，，，，旋轉(zhuǎn)過后可能就是，，，，，，。想法因為這是一個經(jīng)過旋轉(zhuǎn)的升序數(shù)組，我們可以將其看作兩個升序的序列，，，和，，。如果在前一個序列，則從前面進行查找。如果在后面一個序列，則從最后一個元素開始查找。 題目詳情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume NO duplicates in the a...
閱讀 3325·2021-11-12 10:36
閱讀 2483·2021-11-02 14:43
閱讀 2156·2019-08-30 14:23
閱讀 3471·2019-08-30 13:08
閱讀 928·2019-08-28 18:09
閱讀 3141·2019-08-26 12:22
閱讀 3155·2019-08-23 18:24
閱讀 2025·2019-08-23 18:17
