c++ 使用二进制搜索查找元素的第一个和最后一个位置时测试用例失败

von4xj4u  于 2023-08-09  发布在  其他
关注(0)|答案(1)|浏览(95)

给定一个以非降序排序的整数nums数组,查找给定目标值的开始和结束位置。
如果在数组中找不到目标,则返回[-1,-1]。
你必须编写一个运行时复杂度为O(log n)的算法。
我用leetcode写了这段代码,但它只通过了88个测试用例中的67个。有人能告诉我这段代码的问题吗?

class Solution {
public:
int FirstOccurence(vector<int> arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        // maybe an answer
        if (arr[mid] == x) {
            ans=mid;
            high=mid-1;
    }
    else if (arr[mid]< x) {
            low=mid+1;
    }
    else high=mid-1;
    }
    return ans;
}

int LastOccurence(vector<int> arr, int n, int x) {
    int low = 0, high = n - 1;
    int ans = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        // maybe an answer
        if (arr[mid]== x) {
            ans = mid;
            //look for smaller index on the left
            low=mid+1;
        }
        else if(arr[mid]>x){
            high=mid-1;
        }
        else {
            low = mid + 1; // look on the right
        }
    }
    return ans;
}
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size()-1;
        int k=target;
        int a=FirstOccurence(nums,n,k);
    int b=LastOccurence(nums,n,k);
    return{a,b};
    }
};

字符串

bbuxkriu

bbuxkriu1#

您将nums.size() - 1发送到二进制搜索函数,并在其中生成high = n - 1,实际上生成high = nums.size() - 2,因此所有targetvector中最大数字的测试都将失败。
一个简单的解决方法是根本不发送n。您已经发送了vector,并且可以在函数内部调用.size()

int FirstOccurence(const std::vector<int>& arr, int x) {  // no `n`
    int low = 0, high = static_cast<int>(arr.size()) - 1; // size() - 1 instead

个字符
然后在呼叫现场:

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
    int k = target;
    int a = FirstOccurence(nums, k); // no `n`
    int b = LastOccurence(nums, k);  // no `n`
    return {a, b};
}


另一种方法是使用标准库中的std::equal_range

#include <algorithm> // equal_range
#include <iterator>  // distance

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
    std::vector<int> res{-1, -1};
    auto [fit, lit] = std::equal_range(nums.begin(), nums.end(), target);

    if (fit != lit) {
        res[0] = static_cast<int>(std::distance(nums.begin(), fit));
        res[1] = static_cast<int>(std::distance(nums.begin(), lit)) - 1;
    }
    return res;
}

相关问题