Is it cheating for this solution in Java?


  • 0
    G

    The idea to solve this problem is extremely clear and simple:

    1. Find the index of the smallest number;
    2. Split the array into two ordered parts at the index;
    3. Use Arrays.binarySearch(..) to find the answer.

    On the third step, I feel like it is cheating. What's your thought on this?

    public int search(int[] A, int target) {
    	if (A == null || A.length == 0) {
    		return -1;
    	}
    	int pivot = indexOfMin(A, 0, A.length - 1);
    	
    	int resL = Arrays.binarySearch(A, 0, pivot, target);		
    	if (resL >= 0)
    		return resL;
    	
    	int resR = Arrays.binarySearch(A, pivot, A.length, target);
    	if (resR >= 0)
    		return resR;
    	
    	return -1;
    
    }
    
    public int indexOfMin(int[] A, int start, int end) {
    	if (A[start] <= A[end]) {
    		return start;
    	}
    	int mid = (start + end) / 2;
    
    	int i = indexOfMin(A, start, mid); // min index of left half
    	int j = indexOfMin(A, mid + 1, end); // min index of right half
    
    	return A[i] < A[j] ? i : j;
    }

  • 0
    S

    Looks good! I like your neat idea.


Log in to reply
 

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