https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
- This is a follow up problem to Search in Rotated Sorted Array, where
numsmay contain duplicates. - Would this affect the run-time complexity? How and why?
代码：
class Solution {
public:
bool search(vector<int>& nums, int target) {
vector<int> ans;
int t = target;
if(target == 0) ans.push_back(0);
while(target) {
ans.push_back(target % 10);
target /= 10;
}
sort(ans.begin(), ans.end());
int n = nums.size();
map<int, int> vis;
for(int i = 0; i < n; i ++)
vis[nums[i]] ++;
if(t > 10) {
for(int i = 0; i < n; i ++)
if(nums[i] == t) return true;
return false;
}
for(int i = 0; i < ans.size(); i ++) {
vis[ans[i]] --;
if(vis[ans[i]] < 0) return false;
}
return true;
}
};