今天的題目是 33. Search in Rotated Sorted Array,給定一個排序但被旋轉過的陣列,找出某個數字在第幾個 index,題目限定必須要在 O(logN)之內完成。

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

救急偷吃步方法:(我一開始以為會TLE結果AC了❗❗)

int search(vector<int>& nums, int target) {
        vector<int>::iterator it = find(nums.begin(), nums.end(), target);
        if (it != nums.end())
	        return distance(nums.begin(), it);
        else
            return 0;
    }

當然還是要尋求解法:初步想法是先用 binary search 找到旋轉點(後者比前者小),接著再看是要用前面或後面來做 binary search。

class Solution {
public:
    int binarySearch(vector<int>& nums, int low,  
                      int high, int key) 
    { 
      if (high < low) 
        return -1; 

      int mid = (low + high)/2;
      if (key == nums[mid]) 
        return mid; 

      if (key > nums[mid]) 
        return binarySearch(nums, (mid + 1), high, key); 

        return binarySearch(nums, low, (mid -1), key); 
    } 

    int findPivot(vector<int>& nums, int low, int high) 
    { 
      if (high < low) return -1; 
      if (high == low) return low; 

       int mid = (low + high)/2;
       if (mid < high && nums[mid] > nums[mid + 1]) 
        return mid; 

       if (mid > low && nums[mid] < nums[mid - 1]) 
        return (mid-1); 

       if (nums[low] >= nums[mid]) 
        return findPivot(nums, low, mid-1); 

       return findPivot(nums, mid + 1, high); 
    }

    int search(vector<int>& nums, int target) {
      int pivot = findPivot(nums, 0, nums.size()-1);

      if (pivot == -1) 
        return binarySearch(nums, 0, nums.size()-1, target); 

      if (nums[pivot] == target) 
        return pivot; 

      if (nums[0] <= target) 
        return binarySearch(nums, 0, pivot-1, target); 

        return binarySearch(nums, pivot+1, nums.size()-1, target); 
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料