別眨眼網

題目

假設按照升序排序的陣列在預先未知的某個點上進行了旋轉。（ 例如，陣列 ［0，0，1，2，2，5，6］ 可能變為 ［2，5，6，0，0，1，2］ ）。編寫一個函式來判斷給定的目標值是否存在於陣列中。若存在返回 true，否則返回 false。示例 1：輸入： nums = ［2，5，6，0，0，1，2］， target = 0輸出： true示例 2：輸入： nums = ［2，5，6，0，0，1，2］， target = 3輸出： false進階：這是 搜尋旋轉排序陣列 的延伸題目，本題中的 nums  可能包含重複元素。這會影響到程式的時間複雜度嗎？會有怎樣的影響，為什麼？

解題程式碼與測試

//// Created by tannzh on 2020/8/18。///* *假設按照升序排序的陣列在預先未知的某個點上進行了旋轉。（ 例如，陣列 ［0，0，1，2，2，5，6］ 可能變為 ［2，5，6，0，0，1，2］ ）。編寫一個函式來判斷給定的目標值是否存在於陣列中。若存在返回 true，否則返回 false。示例 1：輸入： nums = ［2，5，6，0，0，1，2］， target = 0輸出： true示例 2：輸入： nums = ［2，5，6，0，0，1，2］， target = 3輸出： false進階：這是 搜尋旋轉排序陣列 的延伸題目，本題中的 nums  可能包含重複元素。這會影響到程式的時間複雜度嗎？會有怎樣的影響，為什麼？ */#include #include using std：：vector；class Solution {public： bool search（vector& nums， int target） { int n = nums。size（）， left = 0， right = n - 1； while （left <= right） { int mid = （left + right） / 2； if （nums［mid］ == target） return true； if （nums［mid］ < nums［right］） { if （nums［mid］ < target && nums［right］ >= target） left = mid + 1； else right = mid - 1； } else if （nums［mid］ > nums［right］）{ if （nums［left］ <= target && nums［mid］ > target） right = mid - 1； else left = mid + 1； } else ——right； } return false； }}；int main（int argc， char **argv）{ std：：vector nums1 = {2，5，6，0，0，1，2}； int target1 = 0； std：：vector nums2 = {2，5，6，0，0，1，2}； int target2 = 3； Solution s； std：：cout << s。search（nums1， target1） << std：：endl； std：：cout << s。search（nums2， target2） << std：：endl； return 0；}

解題思路分析

這道是之前那道 Search in Rotated Sorted Array 的延伸，現在陣列中允許出現重複數字，這個也會影響我們選擇哪半邊繼續搜尋，由於之前那道題不存在相同值，我們在比較中間值和最右值時就完全符合之前所說的規律：

如果中間的數小於最右邊的數，則右半段是有序的，若中間數大於最右邊數，則左半段是有序的

。而如果可以有重複值，就會出現下面兩種情況，［3 1 1］ 和 ［1 1 3 1］，對於這兩種情況中間值等於最右值時，目標值3既可以在左邊又可以在右邊，那怎麼辦麼，對於這種情況其實處理非常簡單，只要把最右值向左一位即可繼續迴圈，如果還相同則繼續移，直到移到不同值為止，然後其他部分還採用 Search in Rotated Sorted Array 中的方法，可以得到程式碼如上。