資訊專欄INFORMATION COLUMN
摘要：題目要求相比于，中添加了數(shù)組中可能存在重復(fù)值的條件。這是我們可以將情況分為以下幾種。因?yàn)槿绻?，則左側(cè)或右側(cè)的子數(shù)組至少有一個(gè)為順序的數(shù)組，這違背題目要求。所喲一定是同理，如果，那么。
題目要求
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中添加了數(shù)組中可能存在重復(fù)值的條件。大家可以先參考一下我的這篇關(guān)于I的博客，在這個(gè)基礎(chǔ)上，考慮如何實(shí)現(xiàn)這道題目。
思路與代碼在上一道題目的基礎(chǔ)上，我們知道，如果數(shù)組中存在重復(fù)值，可能會(huì)出現(xiàn)類似于[1,3,1,1]這種情況出現(xiàn)。如果在這時(shí)候使用二分法，很可能會(huì)無法判斷出到底屬于左半側(cè)數(shù)組還是右半側(cè)數(shù)組。這是我們可以將情況分為以下幾種。
目標(biāo)值位于左側(cè)上升數(shù)組中，也就是說nums[left] 目標(biāo)值位于右側(cè)上升數(shù)組中，也就是說nums[mid] 其它情況 在第三種情況下，我們可以看到該類別滿足nums[left]>=nums[mid]且nums[mid]>=nums[right]。這時(shí)候，我們可以分析一下， 如果nums[mid]>nums[right]，那么nums[mid]=nums[left]。因?yàn)槿绻鹡ums[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;
}
//判斷左右節(jié)點(diǎn)是否為目標(biāo)值，不是則分別調(diào)整
}else{
if(nums[left] == target || nums[right] == target){
return true;
}else{
left++;
right--;
}
}
}
return false;
}
簡單優(yōu)化
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;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67230.html
摘要：如果左邊的點(diǎn)比右邊的大，說明這兩個(gè)點(diǎn)之間有一個(gè)旋轉(zhuǎn)點(diǎn)，導(dǎo)致了不再有序。因?yàn)橹挥幸粋€(gè)旋轉(zhuǎn)點(diǎ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...
摘要：找中點(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 ...
摘要：這里相比于思路一，更適用于目標(biāo)節(jié)點(diǎn)在中間的情況，而思路一在目標(biāo)節(jié)點(diǎn)分布在數(shù)組兩側(cè)會(huì)效率更高。 題目要求 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)過后可能就是，，，，，，。想法因?yàn)檫@是一個(gè)經(jīng)過旋轉(zhuǎn)的升序數(shù)組，我們可以將其看作兩個(gè)升序的序列，，，和，，。如果在前一個(gè)序列，則從前面進(jìn)行查找。如果在后面一個(gè)序列，則從最后一個(gè)元素開始查找。 題目詳情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
摘要：二分迭代法復(fù)雜度時(shí)間空間遞歸棧空間思路找旋轉(zhuǎn)數(shù)組的起點(diǎn)，實(shí)際上類似找一個(gè)山谷，只要兩邊都比中間高就對(duì)了，這和這題很像。 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 ...
閱讀 3569·2023-04-25 16:35
閱讀 714·2021-10-11 11:09
閱讀 6192·2021-09-22 15:11
閱讀 3363·2019-08-30 14:03
閱讀 2604·2019-08-29 16:54
閱讀 3356·2019-08-29 16:34
閱讀 3063·2019-08-29 12:18
閱讀 2132·2019-08-28 18:31
