LeetCode 34 Find First and Last Position of Element in Sorted Array

Tag: LeetCode 二分搜索 Posted on 2021-05-25 10:12:27 Edited on 2021-05-25 10:20:55 Views: 55

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目分析

二分搜索的变种题,要求 O(log n) 的时间复杂度。

4ms 的解法

很直白的解法,第一步先找出一个目标值所在的位置,第二步分别向左向右遍历以找到边界。

其中第一步是 O(log n),第二步在最坏情况下是 O(n),最坏的情况为首尾两端非目标值,其余均为目标值。

但是 LeetCode 依然给让过了。

class Solution {
public:
    vector<int> nums;
    int target;
    
    vector<int> searchRange(vector<int>& nums, int target) {
        this->nums = nums;
        this->target = target;
        vector<int> ans = {-1, -1};
        if (nums.size() == 0) return ans;
        int pos = helper(0, nums.size()-1);
        if (pos == -1) return ans;
        ans[0] = pos;
        ans[1] = pos;
        while(ans[0]-1 >= 0 && nums[ans[0]-1] == target) ans[0]--;
        while(ans[1]+1 < nums.size() && nums[ans[1]+1] == target) ans[1]++;
        return ans;
    }
    
    int helper(int l, int r) {
        if (l > r) return -1;
        if (nums[l] == target) return l;
        if (nums[r] == target) return r;

        int m = (l + r) / 2;
        if (nums[m] == target) return m;
        if (nums[m] > target) {
            return helper(l+1, m-1);
        } else {
            return helper(m+1, r-1);
        }
    }
};

0ms 的解法

看了一个示例代码,换成迭代的形式就可以做到 0ms,其代码有点烂就不放了。

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