LeetCode 81 Search in Rotated Sorted Array II

标签: 二分搜索 LeetCode 发布于:2022-03-26 11:07:39 编辑于:2022-03-26 11:51:10 浏览量:418

概述

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

暴力法

直接暴力遍历。

二分搜索

分类讨论就好了,258 / 279 test cases passed

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                return true;
            } else if (nums[m] < target) {
                l = m + 1;
            } else { // nums[m] > target
                if (target >= nums[0]) {
                    r = m - 1;
                } else {
                    if (nums[m] >= nums[0]) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
            }
        }
        return false;
    }
};

但是由于相同值的存在上面分类讨论的假设可能并不成立。

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28218/My-8ms-C%2B%2B-solution-(o(logn)-on-average-o(n)-worst-case)

哇,是真的恶心,折磨了我好久:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                return true;
            } else if (nums[l] == nums[m] && nums[r] == nums[m]) {
                l ++;
                m --;
            } else if (nums[l] <= nums[m]) {
                if (nums[m] < target) {
                    l = m + 1;
                } else {
                    if (target >= nums[l]) {
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                }
            } else { // nums[l] > nums[m]
                if (nums[m] < target) {
                    if (target >= nums[l]) {
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                } else {
                    r = m - 1;
                }
            }
        }
        return false;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/