程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode從零單刷]Search in Rotated Sorted Array I & II

[LeetCode從零單刷]Search in Rotated Sorted Array I & II

編輯:關於C++

I 題目:

 

Suppose a sorted array 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.

解答:

直接遍歷是可以的,但是不夠快。再想想,已經 sorted 了,能不能用 O(log n) 時間復雜度的方法?二分搜索?

二分搜索需要探究 mid 處的值與 target 的關系,因此將原數組分為head~mid、mid~tail 兩個區間繼續二分。

但是對於 rotated 的特殊排序數組,可能有以下兩種特殊情況:

[4,5,6,7,8,1,2],中間值是 7,大於 tail=2。但是 head~mid 區間內必然是有序的,如果 [head] < target < [mid],可以正常二分;如果不在,就繼續對特殊區間 mid~tail 特殊二分處理
[4,5,6,0,1,2,3],中間值是 0,小於 head=4,但是 mid~tail 區間內必然是有序的,如果 [mid] < target < [tail],可以正常二分;如果不在,就繼續對特殊區間 head~mid 特殊二分處理

關於二分搜索的實現,有一個細節需要注意:每次必然移動一位

例如:head = mid +1,tail = mid - 1。只是這樣實現,需要在循環中單獨預先判斷 head,tail,mid 處的值。

 

class Solution {
public:
    int search(vector& nums, int target) {
        int size = nums.size();
        int mid;
        int head = 0;
        int tail = size - 1;
        
        while (head <= tail) {
            if (nums[head] == target)   return head;
            if (nums[tail] == target)   return tail;
            mid = (head + tail) / 2;
            if (nums[mid] == target)    return mid;
        
            if (nums[mid] < nums[head]) {
                if (nums[mid] < target && target < nums[tail]) head = mid + 1;
                else tail = mid - 1;
            }
            else if (nums[mid] > nums[tail]) {
                if (nums[head] < target && target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
            else {
                if (target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
        }
        return -1;
    }
};

II 題目:

 

 

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

解答:

如果有重復元素,例如 [1,2,1,1]。那麼中間值是大於 tail 時, head~mid 區間內未必是有序的;同理中間值是小於 head 時, mid~tail 區間內未必是有序的。

但是,如果我跳過重復元素呢?就變成了上一道問題了。因此,這道題僅僅需要一些預處理過程。

 

class Solution {
public:
    bool search(vector& nums, int target) {
        int size = nums.size();
        int mid;
        int head = 0;
        int tail = size - 1;
        
        while (head <= tail) {
            if (nums[head] == target)   return true;
            if (nums[tail] == target)   return true;
            mid = (head + tail) / 2;
            if (nums[mid] == target)    return true;
        
            if (nums[mid] == nums[head]) {
                int i = head;
                for(; i <= mid; i++) {
                    if (nums[i] != nums[mid]) {
                        head = i;
                        break;
                    }
                }
            }
            
            if (nums[mid] == nums[tail]) {
                int i = tail;
                for(; i >= mid; i--) {
                    if (nums[i] != nums[mid]) {
                        tail = i;
                        break;
                    }
                }
            }
            
            if (nums[mid] < nums[head]) {
                if (nums[mid] < target && target < nums[tail]) head = mid + 1;
                else tail = mid - 1;
            }
            else if (nums[mid] > nums[tail]) {
                if (nums[head] < target && target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
            else {
                if (target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
        }
        return false;
    }
};

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved