Where is the difference between those two JAVA solutions?


  • 0
    L

    Depend on the test cases? I'm confused.
    2ms

    public class Solution {
        public boolean search(int[] nums, int target) {
            return helper(nums, target, 0, nums.length-1);
        }
        private boolean helper(int[] nums, int target, int left, int right) {
            if (left > right) return false;
            int mid = (left+right)/2;
            if (nums[mid] == target) return true;
            else if (target < nums[mid]) return helper(nums, target, left, mid-1) || helper(nums, target, mid+1, right);
            else return helper(nums, target, mid+1, right) || helper(nums, target, left, mid-1);
        }
    }
    

    1ms

    public class Solution {
        public boolean search(int[] nums, int target) {
            return helper(nums, target, 0, nums.length-1);
        }
        private boolean helper(int[] nums, int target, int left, int right) {
            if (left > right) return false;
            int mid = (left+right)/2;
            if (nums[mid] == target) return true;
            else return helper(nums, target, left, mid-1) || helper(nums, target, mid+1, right);
        }
    }
    

  • 0

    @lxyscls Two major reasons here:

    • the previous solution is complicated though it might seem quite the same logically but the compiling and optimising process will not the same
    • the OJ sometimes just fluctuate so as long as the time cost differs not too much, it's acceptable

    Algorithm is the key here, in fact I think iterative can be better in this problem; here is a C++ solution for reference.

    class Solution {
    public:
        bool search(vector<int>& nums, int target) 
        {
            if(nums.empty()) return false;
            int l = 0, r = nums.size()-1;
            while(l < r)
            {
                int m = l+(r-l)/2;
                if(nums[m] == target) return true;
                if(nums[m] > nums[r]) 
                {
                    if(nums[l]<=target && nums[m]>target) r = m-1;
                    else l = m+1;
                }
                else if(nums[m] < nums[r])
                {
                    if(nums[m]<target && nums[r]>=target) l = m+1;
                    else r = m;
                }
                else r--;
            }
            return nums[l] == target;
        }
    };
    

Log in to reply
 

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