資訊專欄INFORMATION COLUMN
摘要：這里相比于思路一，更適用于目標(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 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.
翻譯過來就是說：一個(gè)由小到大有序排列的數(shù)組被分為兩個(gè)子數(shù)組，這兩個(gè)子數(shù)組調(diào)換前后順序生成一個(gè)新數(shù)組。在新數(shù)組中找到目標(biāo)值并返回下標(biāo)
思路一：雙指針左右同時(shí)比較，直至找到目標(biāo)值或是左右指針相遇
public int search(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left<=right){
if(nums[left]==target){
return left;
}
if(nums[right] == target){
return right;
}
left++;
right--;
}
return -1;
}
思路二：二分法查找
思路一并沒有充分利用條件，及這個(gè)數(shù)組是由兩個(gè)有序的子數(shù)組合成的。這里我們可以使用二分法的一個(gè)變形的算法。先找到中間節(jié)點(diǎn)，這個(gè)中間節(jié)點(diǎn)如果不是在左順序子數(shù)組，就一定在右順序子數(shù)組，反之亦成立。這樣我們就可以變相的使用二分法將區(qū)間范圍逐漸縮小，直至找到目標(biāo)值。
這里相比于思路一，更適用于目標(biāo)節(jié)點(diǎn)在中間的情況，而思路一在目標(biāo)節(jié)點(diǎn)分布在數(shù)組兩側(cè)會(huì)效率更高。
public int search(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left<=right){
int mid = (left + right)/2;
int midNum = nums[mid];
if(midNum==target){
return mid;
}
if(nums[left]<=midNum){
if(nums[left]<=target && midNum>target){
right = mid - 1;
}else{
left = mid + 1;
}
}
if (midNum <= nums[right]){
if (target > midNum && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
想要了解更多開發(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://specialneedsforspecialkids.com/yun/67054.html
摘要：如正常的升序排列應(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...
摘要：由于不是一直升序，所以需要多些條件進(jìn)行范圍的限定。注意邊界值的確定，有邊界值相等，列表只有一個(gè)值，這些情況。注意的使用應(yīng)用排序，快速確定某個(gè)值的位置 題目闡釋： 給定一組升序數(shù)組，取某個(gè)點(diǎn)之后將數(shù)組截?cái)嘟粨Q前后兩個(gè)數(shù)組順序， 給定一個(gè)值，求這個(gè)值的index 重點(diǎn)：二分法，確定target在哪個(gè)列表中，之后不斷二分法進(jìn)行位置確認(rèn)。 由于不是一直升序，所以需要多些條件進(jìn)行范圍的限定...
摘要：如果左邊的點(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 ...
摘要：題目要求相比于，中添加了數(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. ...
閱讀 3333·2021-11-22 14:44
閱讀 2537·2019-08-30 14:10
閱讀 2589·2019-08-30 13:12
閱讀 1217·2019-08-29 18:36
閱讀 1341·2019-08-29 16:16
閱讀 3328·2019-08-26 10:33
閱讀 1761·2019-08-23 18:16
閱讀 379·2019-08-23 18:12
