【問題描述】[33. 搜索旋轉排序數(shù)組] [中等]

假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉。( 例如，數(shù)組?[0,1,2,4,5,6,7]?可能變?yōu)?[4,5,6,7,0,1,2]?)。搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回?-1?。你可以假設數(shù)組中不存在重復的元素。你的算法時間復雜度必須是?O(log?n) 級別。示例 1:輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4

【解答思路】

1. 暴力法 （不符合題意）

時間復雜度：O(N) 空間復雜度：O(1)

public class Solution {public int search(int[] nums, int target) {int len = nums.length;for (int i = 0; i < len; i++) {if (nums[i] == target) {return i;}}return -1;} }

2. 二分查找 修改版

時間復雜度：O(logN) 空間復雜度：O(1)

public int search(int[] nums, int target) {int left= 0;int right = nums.length-1;while(left <=right){int mid = (right - left ) /2 +left;if(target == nums[mid] ){return mid;}先根據(jù) nums[mid] 與 nums[lo] 的關系判斷 mid 是在左段還是右段 if(nums[mid] <nums[right]){if (nums[mid] <= target && target <= nums[right]) {// 下一輪搜索區(qū)間是 [mid+1, right]left = mid+1;} else {// 只要上面對了，這個區(qū)間是上面區(qū)間的反面區(qū)間，下一輪搜索區(qū)間是 [left, mid - 1]right = mid - 1;}}else{ // [left, mid] 有序，但是為了和上一個 if 有同樣的收縮行為，// 當區(qū)間只有 2 個元素的時候 int mid = (left + right + 1) >>> 1; 一定會取到右邊// 此時 mid - 1 不會越界，就是這么剛剛好if (nums[left] <= target && target <= nums[mid]) {/// 下一輪搜索區(qū)間是 [left, mid - 1]right = mid-1;} else {// 下一輪搜索區(qū)間是 [mid+1, right]left = mid+1;}}}return -1 ;}

3. 有序數(shù)組查找目標值 + 二分查找

class Solution {public int search(int[] nums, int target) {int lo = 0, hi = nums.length - 1;while (lo <= hi) {int mid = lo + (hi - lo) / 2;if (nums[mid] == target) {return mid;}// 先根據(jù) nums[0] 與 target 的關系判斷目標值是在左半段還是右半段if (target >= nums[0]) {// 目標值在左半段時，若 mid 在右半段，則將 mid 索引的值改成 infif (nums[mid] < nums[0]) {nums[mid] = Integer.MAX_VALUE;}} else {// 目標值在右半段時，若 mid 在左半段，則將 mid 索引的值改成 -infif (nums[mid] >= nums[0]) {nums[mid] = Integer.MIN_VALUE;}}if (nums[mid] < target) {lo = mid + 1;} else {hi = mid - 1;}}return -1;} }

【總結】

1. 二分查找模板[詳解鏈接]

int binary_search(int[] nums, int target) {int left = 0, right = nums.length - 1; // <=while(left <= right) {int mid = left + (right - left) / 2;//防止大數(shù)溢出if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1; } else if(nums[mid] == target) {// 直接返回return mid;}}// 直接返回return -1; }

2. 排除法找規(guī)律分析 不要想著一蹴而就

• 有序增長的部分分開思考 一蹴而就
• if -else 好想的條件放進if 其余else

3. 該有的模板初期要不斷總結 根據(jù)模板發(fā)散思考 切忌想當然

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第33题][搜索旋转排序数组]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。