Require admin to update test cases


  • 5
    J

    I think it's necessary to update test cases. The reason is as follows:

    when I easily try to find the target one by one in the array and it's a O(n) algorithm, it costs 4ms,
    the O(n) solution:

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            for(int i=0; i<nums.size(); i++)
                if(nums[i] == target)
                    return i;
            return -1;
        }
    };
    

    however, when I first find the min index using binary search, and search the target using binary search again, which is a O(lgn) algorithm, it costs 12ms!
    the O(logn) solution:

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            if(nums.size()==0)
                return -1;
    
            int p = min_index(nums);
            if(target < nums[p] || target > nums[p==0?(nums.size()-1):(p-1)])
                return -1;
            if(p==0)
            {
                return binary_search(nums, 0, nums.size()-1, target);
            }
            if(target == nums[nums.size()-1])
                return nums.size()-1;
            else if(target < nums[nums.size()-1])
                return binary_search(nums, p, nums.size()-1, target);
            else
                return binary_search(nums, 0, p-1, target);
        }
        
        
        int binary_search(vector<int> &v, int left, int right, int val)
        {
            while(left<=right) {
                int m = (left+right)/2;
                if(v[m] == val)
                    return m;
                if(v[m] > val)
                    right = m-1;
                else
                    left = m+1;
            }
            return -1;
        }
        
        int min_index(vector<int> &nums)
        {
            int left = 0, right = nums.size()-1;
            while(left <= right) {
                if(nums[left] < nums[right])
                    return left;
                
                int mid = (left+right)/2;
                if(nums[mid] > nums[left])
                    left = mid;
                else if(nums[mid] < nums[left])
                    right = mid;
                else {
                    return nums[left] < nums[right] ? left:right;
                }
            }
        }
    };

  • 1
    D

    It make sense, O(N) runtime is not necessary longer than O(logN), It is necessary only when N is infinite.


Log in to reply
 

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