Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Search for a Range

Leetcode algorithms 第 34 题:Search for a Range 。

题目

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解答1

寻找已排序数组中的某个数字出现的起始位置,可以直接使用STL中的equal_range函数,但注意该函数返回的是开始位置和结束位置的下一个位置。另外也要注意元素不存在的情况。

具体代码如下:

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        pair<int*, int*> p = equal_range(A, A + n, target);
        vector<int> ans;
        if (p.first == p.second) //没找到
            ans.push_back(-1), ans.push_back(-1);
        else                    //注意末尾位置为实际的target最后出现的下一个位置
            ans.push_back(p.first - A), ans.push_back(p.second - A - 1);
        return ans;
    }
};

解答2

可以自己使用二分查找进行寻找,首先寻找大于或等于target的第一个元素,然后寻找小于或等于target的最后一个元素,即为代码中的st1和st2,那么答案就是[st1, st2]。注意代码中求st2时有一个条件分支是st2=mid,这在st+1==ed的情况下会产生死循环,因为st和ed的平均数还是st。可以改变这里求平均数的策略,使得相邻两个数的平均数为后一个数,即刚刚st和ed的平均数为ed。

另外,st2也可以变为大于target的第一个元素,即为STL的思路,此时答案为[st1, st2-1]。

代码如下:

class Solution {
public: 
    vector<int> searchRange(int A[], int n, int target) {
        int st1 = 0, ed1 = n - 1; //st1为大于或等于target的第一个元素
        while (st1 < ed1)
        {
            int mid = st1 + ((ed1 - st1) >> 1);
            if (A[mid] >= target) ed1 = mid;
            else st1 = mid + 1;
        }
        
        int st2 = 0, ed2 = n - 1; //st2为小于或等于target的最后一个元素
        while (st2 < ed2) 
        {
            int mid = st2 + ((ed2 - st2 + 1) >> 1); //这里加1以避免死循环
            if (A[mid] <= target) st2 = mid;
            else ed2 = mid - 1;
        }
        
        if (A[st1] != target) st1 = st2 = -1; //没找到
        
        vector<int> ans;
        ans.push_back(st1);
        ans.push_back(st2);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论