Is My Code Error Or The LeetCodeOJ's Bug?


  • 0

    Hello, everyone, this is my code for Search for a Range, it's main idea is binary search. But in the submission, LeetCodeOj give me the follow Warning! What Wrong? Actually, the output is [7,7] in msvc2010 when input is [0,0,2,3,4,4,4,5], 5, so how do you explain this warning? Why the output in the web is [7,8]?

    Wrong Answer:

    Input:	[0,0,2,3,4,4,4,5], 5
    Output:	[7,8]
    Expected:	[7,7]
    

    C++ Code:

    #include <iostream>
    #include <vector>
    class Solution
    {
    public:
        std::vector<int> searchRange(int A[], int n, int target)
        {
            std::vector<int> result;
    		int mid = (n - 1) / 2;
            if (n < 1 || A[0] > target || A[n - 1] < target)
            {
                result.push_back(-1);
                result.push_back(-1);
            }
            else if (A[mid] < target)
            {
                result = searchRange(A + mid + 1, n - mid - 1, target);
    			if (result[0] != -1)
    			{
    				result[0] += mid + 1;
    				result[1] += mid + 1;
    			}
            }
            else if (A[mid] > target)
            {
                result = searchRange(A, mid + 1, target);
            }
            else
            {
    			result.push_back(searchMinPos(A, mid + 1, target));
    			result.push_back(mid + 1 + searchMaxPos(A + mid + 1, n - mid - 1, target));
            }
    		return result;
        }
        int searchMinPos(int A[], int n, int target)
        {
            int low = 0, high = n - 1;
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (A[mid] < target)
                {
                    low = mid + 1;
                }
                else if (A[mid] > target)
                {
                    high = mid - 1;
                }
                else if (mid == 0 || A[mid - 1] != target)
                {
                    return mid;
                }
                else
                {
                    high = (low + high) % 2 ? (mid - 1) : mid;
                }
            }
            return -1;
        }
        int searchMaxPos(int A[], int n, int target)
        {
            int low = 0, high = n;
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (A[mid] < target)
                {
                    low = mid + 1;
                }
                else if (A[mid] > target)
                {
                    high = mid - 1;
                }
                else if (mid == n - 1 || A[mid + 1] != target)
                {
                    return mid;
                }
                else
                {
                    low = (low + high) % 2 ? (mid + 1) : mid;
                }
            }
            return -1;
        }
    };
    int main(int argc, char const *argv[])
    {
    	Solution sol;
    	int A[] = {0,0,2,3,4,4,4,5};
    	std::vector<int> result = sol.searchRange(A, 8, 5);
    	for (std::size_t i = 0; i != result.size(); ++i)
    	{
    		std::cout << result[i] << " ";
    	}
    	std::cout << std::endl;
    	getchar();
    	return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.