LeetCode之Search in Rotated Sorted Array二

古城微笑少年丶 2022-08-05 12:17 135阅读 0赞

题目：Follow 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.

分析：与上题不同的是允许数组中有重复的元素，这个时候就只需要特殊处理这个相同的元素即可。

代码：

class Solution2{
    public:
    	int search(int A[], int n, int target) {
    		int first =0 ;int last = n;
    		while(first != last){
    			int mid = (first + last)/2;
    			if (A[mid] == target){
    				return mid;
    			}
    
    			if (A[first] < A[mid]){ //first到mid之间元素内有序，那么就在该段内尝试查找
    				//判断target是否在范围之内
    				if (A[first]<=target && target < A[mid]){
    					last = mid;
    				}else{
    					first = mid + 1;
    				}
    			}else if(A[first] > A[mid]){ //first到mid之间元素无序,那么这时后半部分有序，尝试查找。
    				//判断target是否在范围之内
    				if (A[mid] < target && target <= A[last - 1]){
    					first = mid + 1;
    				}else{
    					last = mid;
    				}
    			}else{//处理重复元素的情况
    				first++ ;//直接略过该元素
    			}
    		}
    		return -1;
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 33. Search in Rotated Sorted Array

Topic Array Binary Search Description [https://leetcode.com/problems/search

红太狼/ 2023年01月04日 11:53/ 0 赞/ 142 阅读

相关 LeetCode81——Search in Rotated Sorted Array II

LeetCode81——Search in Rotated Sorted Array II 加入重复数据的Search in Rotated Sorted Array

小灰灰/ 2022年08月20日 02:30/ 0 赞/ 17 阅读

相关 Search in Rotated Sorted Array--LeetCode

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.

红太狼/ 2022年08月05日 13:14/ 0 赞/ 8 阅读

相关 LeetCode之Search in Rotated Sorted Array二

题目：Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Wou

古城微笑少年丶/ 2022年08月05日 12:17/ 0 赞/ 136 阅读

相关 LeetCode之Search in Rotated Sorted Array

题目：Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0

喜欢ヅ旅行/ 2022年08月05日 12:17/ 0 赞/ 124 阅读

相关 33. Search in Rotated Sorted Array

描述： Suppose an array sorted in ascending order is rotated at some pivot unknown to you

深藏阁楼爱情的钟/ 2022年06月02日 01:26/ 0 赞/ 142 阅读

相关 python -- leetcode ---- 81.Search in Rotated Sorted Array II

\-81.Search in Rotated Sorted Array II 给定一个list,是由一个有序数组在某一枢纽处旋转得到的,并且其中可能含有重复元素,要求判断

红太狼/ 2022年05月13日 13:44/ 0 赞/ 124 阅读

相关 81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

谁借莪１个温暖的怀抱￠/ 2022年03月07日 14:45/ 0 赞/ 178 阅读

相关 leetcode--Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would

Bertha 。/ 2021年10月16日 01:12/ 0 赞/ 219 阅读

相关【Lintcode】062.Search in Rotated Sorted Array

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,

谁借莪１个温暖的怀抱￠/ 2021年10月01日 01:14/ 0 赞/ 214 阅读