LeetCode / 5 min read
LeetCode - 33. Search in Rotated Sorted Array
LeetCode33
On this page
題目: Search in Rotated Sorted Array
給定一個以升序排列的整數陣列 nums（具有不同的值）。
在傳遞給你的函數之前，可能會在未知的軸心索引 k（1 <= k < nums.length）處對 nums 進行旋轉，
使得結果陣列為
[nums[k]、nums[k+1]、...、nums[n-1]、nums[0]、nums[1]、...、nums[k-1]]（索引從 0 開始）。
例如，[0,1,2,4,5,6,7] 可能會在軸心索引 3 處旋轉，變為 [4,5,6,7,0,1,2]。
給定可能旋轉後的陣列 nums 和一個整數目標 target，如果 target 存在於 nums 中，
則返回其索引；如果不存在，則返回 -1。
你必須使用 O(log n) 的時間複雜度編寫算法。解題思路
由於原本的陣列是升序排列的，所以旋轉後一定至少有一邊是有序的。 以 [4,5,6,7,0,1,2] 為例，左邊 [4,5,6,7] 是有序的，右邊 [0,1,2] 也是有序的。 所以我們可以先判斷左邊或右邊是有序的，再判斷 target 是否在有序的那一邊。 如果是就繼續二分搜尋，如果不是就在另一邊繼續二分搜尋。
步驟:
- 二分搜尋法
- 由於陣列是旋轉過的，所以要先判斷左邊或右邊是有序的
- 再判斷 target 是否在有序的那一邊。 如果是就繼續二分搜尋，如果不是就在另一邊繼續二分搜尋
Code
Java:
Runtime 0 ms(100%), Memory 41.5 MB(96.35%)
class Solution { public int search(int[] nums, int target) { int leftFlag = 0; int rightFlag = nums.length -1; while(leftFlag <= rightFlag){ int midFlag = (leftFlag + rightFlag) / 2; if (nums[midFlag] == target){ return midFlag; } if (nums[leftFlag] <= nums[midFlag]){ // if target is on left side if(nums[leftFlag] <= target && target <= nums[midFlag]){ rightFlag = midFlag -1; }else{ leftFlag = midFlag + 1; } }else{ if(nums[rightFlag] >= target && nums[midFlag] <= target){ leftFlag = midFlag + 1; }else{ rightFlag = midFlag -1; } } } return -1; }}Python3:
Runtime 62 ms(11.45%), Memory 16.7 MB(29.36%)
class Solution: def search(self, nums: List[int], target: int) -> int: left_flag = 0 right_flag = len(nums) - 1 while left_flag <= right_flag: mid_flag = (right_flag + left_flag) // 2 if nums[mid_flag] == target: return mid_flag if nums[left_flag] <= nums[mid_flag]: if nums[left_flag] <= target and nums[mid_flag] >= target: right_flag = mid_flag - 1 else: left_flag = mid_flag + 1 else: if nums[right_flag] >= target and nums[mid_flag] <= target: left_flag = mid_flag + 1 else: right_flag = mid_flag - 1 return -1C#:
Runtime 84 ms(81.86%), Memory 39.3 MB(40.9%)
public class Solution { public int Search(int[] nums, int target) { int LeftFlag = 0; int RightFlag = nums.Length - 1; while (LeftFlag <= RightFlag) { int MidFlag = (LeftFlag + RightFlag) / 2; if (nums[MidFlag] == target){ return MidFlag; } if (nums[LeftFlag] <= nums[MidFlag]){ if (nums[LeftFlag] <= target && target <= nums[MidFlag]){ RightFlag = MidFlag - 1; }else{ LeftFlag = MidFlag + 1; } }else{ if (nums[MidFlag] <= target && target <= nums[RightFlag]){ LeftFlag = MidFlag + 1; }else{ RightFlag = MidFlag - 1; } } } return -1; }}Golang:
Runtime 4 ms(51.96%), Memory 2.5 MB(57.42%)
func search(nums []int, target int) int { leftFlag := 0 rightFlag := len(nums) - 1 for leftFlag <= rightFlag { midFlag := (leftFlag + rightFlag) / 2 if nums[midFlag] == target { return midFlag } if nums[leftFlag] <= nums[midFlag] { if nums[leftFlag] <= target && target <= nums[midFlag] { rightFlag = midFlag - 1 } else { leftFlag = midFlag + 1 } } else { if nums[midFlag] <= target && target <= nums[rightFlag] { leftFlag = midFlag + 1 } else { rightFlag = midFlag - 1 } } } return -1}C++:
Runtime 7 ms(32.87%), Memory 11.1 MB(31.74%)
class Solution {public: int search(vector<int>& nums, int target) { int intLeftFlag = 0; int intRightFlag = nums.size() - 1; while(intLeftFlag <= intRightFlag){ int intMidFlag = (intLeftFlag + intRightFlag) / 2; if(nums[intMidFlag] == target){ return intMidFlag; } if(nums[intLeftFlag] <= nums[intMidFlag]){ if (nums[intLeftFlag] <= target && target <= nums[intMidFlag]){ intRightFlag = intMidFlag - 1; }else{ intLeftFlag = intMidFlag + 1; } }else{ if (nums[intMidFlag] <= target && target <= nums[intRightFlag]){ intLeftFlag = intMidFlag + 1; } else{ intRightFlag = intMidFlag - 1; } } } return -1; }};C:
Runtime 0 ms(100%), Memory 6 MB(64.74%)
int search(int* nums, int numsSize, int target){ int leftFlag = 0; int rightFlag = numsSize - 1; while (leftFlag <= rightFlag) { int midFlag = (leftFlag + rightFlag) / 2; if (nums[midFlag] == target) { return midFlag; } if (nums[leftFlag] <= nums[midFlag]) { if (nums[leftFlag] <= target && target <= nums[midFlag]) { rightFlag = midFlag - 1; } else { leftFlag = midFlag + 1; } } else { if (nums[midFlag] <= target && target <= nums[rightFlag]) { leftFlag = midFlag + 1; } else { rightFlag = midFlag - 1; } } } return -1;}