資訊專欄INFORMATION COLUMN
摘要：題目要求相比于，中添加了數組中可能存在重復值的條件。這是我們可以將情況分為以下幾種。因為如果而且，則左側或右側的子數組至少有一個為順序的數組，這違背題目要求。所喲一定是同理，如果，那么。
題目要求
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 2). Write a function to determine if a given target is in the array. The array may contain duplicates.
相比于I，II中添加了數組中可能存在重復值的條件。大家可以先參考一下我的這篇關于I的博客，在這個基礎上，考慮如何實現這道題目。
思路與代碼在上一道題目的基礎上，我們知道，如果數組中存在重復值，可能會出現類似于[1,3,1,1]這種情況出現。如果在這時候使用二分法，很可能會無法判斷出到底屬于左半側數組還是右半側數組。這是我們可以將情況分為以下幾種。
目標值位于左側上升數組中，也就是說nums[left] 目標值位于右側上升數組中，也就是說nums[mid] 其它情況 在第三種情況下，我們可以看到該類別滿足nums[left]>=nums[mid]且nums[mid]>=nums[right]。這時候，我們可以分析一下， 如果nums[mid]>nums[right]，那么nums[mid]=nums[left]。因為如果nums[mid]>nums[right]而且nums[mid] 同理，如果nums[mid] nums[mid]=nums[left]=nums[right]!=target 代碼如下： public boolean search(int[] nums, int target) {
int left = 0 , right = nums.length-1;
while(left<=right){
int mid = ( left + right ) / 2;
if(nums[mid] == target){
return true;
}else if(nums[left] < nums[mid]){
if(target>=nums[left] && target<=nums[mid]){
right = mid-1;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[right]){
if(target>=nums[mid] && target<=nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
//判斷左右節點是否為目標值，不是則分別調整
}else{
if(nums[left] == target || nums[right] == target){
return true;
}else{
left++;
right--;
}
}
}
return false;
}
簡單優化
public boolean search2(int[] nums, int target){
int left = 0 , right = nums.length-1;
while(left<=right){
int mid = ( left + right ) / 2;
if(nums[mid] == target){
return true;
}else if(nums[left] < nums[mid]){
if(target>=nums[left] && target<=nums[mid]){
right = mid-1;
}else{
left = mid + 1;
}
}else if(nums[mid] < nums[right]){
if(target>=nums[mid] && target<=nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
//精華第三種場景
}else if(nums[mid] > nums[right]){
left = mid + 1;
}else if(nums[mid] < nums[left]){
right = mid - 1;
}else{
left++;
right--;
}
}
return false;
}
想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67230.html
摘要：如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉點，導致了不再有序。因為只有一個旋轉點，所以一分為二后，肯定有一半是有序的。 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...
摘要：找中點若起點小于中點，說明左半段沒有旋轉，否則說明右半段沒有旋轉。在左右半段分別進行二分法的操作。只判斷有無，就容易了。還是用二分法優化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...
摘要：這里相比于思路一，更適用于目標節點在中間的情況，而思路一在目標節點分布在數組兩側會效率更高。 題目要求 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 ...
摘要：如正常的升序排列應該是，，，，，，旋轉過后可能就是，，，，，，。想法因為這是一個經過旋轉的升序數組，我們可以將其看作兩個升序的序列，，，和，，。如果在前一個序列，則從前面進行查找。如果在后面一個序列，則從最后一個元素開始查找。 題目詳情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
摘要：二分迭代法復雜度時間空間遞歸?？臻g思路找旋轉數組的起點，實際上類似找一個山谷，只要兩邊都比中間高就對了，這和這題很像。 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 ...
閱讀 3556·2023-04-25 16:35
閱讀 688·2021-10-11 11:09
閱讀 6138·2021-09-22 15:11
閱讀 3352·2019-08-30 14:03
閱讀 2591·2019-08-29 16:54
閱讀 3343·2019-08-29 16:34
閱讀 3042·2019-08-29 12:18
閱讀 2114·2019-08-28 18:31
