欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode--81. 搜索旋转排序数组Ⅱ(C, Python)

程序员文章站 2022-06-03 11:37:37
...

1. 题目描述

难度:中等
LeetCode--81. 搜索旋转排序数组Ⅱ(C, Python)

2. 题目分析

这道题目是LeetCode–33. 搜索旋转排序数组的延伸题,有三点不一样:

  • 有重复的元素
    数组中的元素虽然是升序的,但是里面含有重复的元素,这相对于33题难度提升了
  • 输出的变量为布尔型变量
    只要求判断数组中是否有元素即可,这相对于33题的输出下标简单一些
  • 不再要求算法复杂度
    不再要求算法复杂度为O(logn),难度直线降低

根据以上分析,可行的算法有两种:

  • 遍历法
    最直接最容易想到的方法就是暴力遍历法,时间复杂度为O(n)。
  • 二分法
    二分法在这道题上相对比较麻烦,我们需要处于数组首尾两个元素出现重复的情况。可以一直判断首尾两个元素是否相等,如果相等,就将末尾元素舍弃掉知道两个元素不等即可。该方法的时间复杂最好的情况是O(logn),最坏的情况是O(n)

3. C语言实现

3.1 遍历法

代码如下:

bool search(int* nums, int numsSize, int target){
    int i;
    for(i = 0; i < numsSize; i++){
        if(target == nums[i])
            return 1;
    }
    return 0;
}

运行结果为:
LeetCode--81. 搜索旋转排序数组Ⅱ(C, Python)

3.2 二分法

代码如下:

bool search(int* nums, int numsSize, int target){
    int left, right, mid;
    left = 0;
    right = numsSize - 1;
    // 如果数组长度为1,直接判断
    if(numsSize == 1) return target==nums[0]?1:0;
    // 如果数组为空,返回0
    if(numsSize == 0) return 0;
    while(left <= right){
    	// 这句话就是防止所有元素都一样的情况
        if(target == nums[left]) return 1;
        // 去掉数组尾部有重复的元素
        while(nums[left] == nums[right] && left < right){
            right--;
        }
        if(target == nums[right]) return 1;
        mid = (left+right)/2;
        if (target == nums[mid]) 
            return 1;
        else if(nums[mid] > nums[right]){
            if(target > nums[left] && target < nums[mid]){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        else{
            if(target > nums[mid] && target < nums[right]){
                left= mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
    }
    return 0;
}

运行结果为:
LeetCode--81. 搜索旋转排序数组Ⅱ(C, Python)

4. Python语言实现

遍历法还是用python实现简单,python大法好。代码如下:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        return True if target in nums else False

运行结果为:
LeetCode--81. 搜索旋转排序数组Ⅱ(C, Python)

相关标签: # •Array