力ボタンブラシ問題33.回転ソート配列の検索(Java)
6376 ワード
タイトル
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).
指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.
配列に重複する要素が存在しないと仮定できます.
あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.
例1:
例2:
構想時間複雑度はO(log n)であり,必ず分治の思想を用いてlognレベルに達する. 二分法により、leftとrightとtargetの関係を判断mid>leftは左半分の秩序if(left midを変更する)を説明する.
問題解
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).
指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.
配列に重複する要素が存在しないと仮定できます.
あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.
例1:
: nums = [4,5,6,7,0,1,2], target = 0
: 4
例2:
: nums = [4,5,6,7,0,1,2], target = 3
: -1
構想
問題解
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if(len < 1) return -1;
int left = 0;
int right = len - 1;
int mid;
while (left<=right){
mid = (left + right)/2;
if(nums[mid] == target){
return mid;
}
if(nums[left] <= nums[mid]){//
if (target >= nums[left] && target < nums[mid]) { // target
right = mid - 1;
} else { //
left = mid + 1;
}
}else{ //
if(target <= nums[right] && target > nums[mid]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
}