本文主要是介绍[LeetCode]81.Search in Rotated Sorted Array II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【题目】
Search in Rotated Sorted Array II
Total Accepted: 3749 Total Submissions: 12937 My SubmissionsFollow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array
【分析】
相比上一道题点击打开链接,这道题允许重复元素出现,则上一道题中的A[start] <= A[mid] 条件就不能确定[start mid]区间为递增有序序列了。
比如:{1,3,1,1,1,1}
如果A[start] <= A[mid] 条件就不能确定[start mid]区间为递增有序序列,我们就把该条件分成两个字条件:
A[start] < A[mid] 则 [start mid]区间为递增有序序列
A[start] = A[mid] 则[start mid]区间不能确定,那就start++,往下一步看看即可。
【代码】
/*********************************
* 日期:2014-01-15
* 作者:SJF0115
* 题号: Search in Rotated Sorted Array II
* 来源:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;class Solution {
public://二分查找bool search(int A[], int n, int target) {int start = 0,end = n-1;int mid;while(start <= end){mid = (start + end) / 2;if(A[mid] == target){return true;}//中间元素大于最左边元素则左部分为有序数组else if(A[mid] > A[start]){//目标位于左部分if(target >= A[start] && target <= A[mid]){end = mid - 1;}//目标位于右部分else{start = mid + 1;}}//中间元素小于最左边元素则右部分为有序数组else if(A[mid] < A[start]){//目标位于右部分if(target <= A[end] && target >= A[mid]){start = mid + 1;}//目标位于左部分else{end = mid - 1;}}//中间元素等于最左边元素则无法区分有序部分else{start++;}}return false;}
};
int main() {int result;Solution solution;int A[] = {4,5,1,2,3};result = solution.search(A,5,4);printf("Result:%d\n",result);return 0;
}
【测试】
[1,1,3,1], 3
[3,1], 1
这篇关于[LeetCode]81.Search in Rotated Sorted Array II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!