Accepted O(???) Java Solution


  • 0
    B

    This was a very trivial problem so I decided to have some fun. Can you figure out the run time? Notice the search pruning from len = r+1, can you figure out another optimization?

    import java.util.Random;
    public class Solution {
        public int searchInsert(int[] A, int target) {
            Random rnd = new Random();
    	    int len = A.length;
    	    for(int i = 0; i < 10000; i++){
        		int r = Math.abs(rnd.nextInt())%len;
        		if(A[r] == target) return r;
        		if(A[r] > target){
        			if(r == 0) return r;
        			if(A[r-1] == target) return r-1;
        			else if(A[r-1]< target) return r;
        			len = r+1;
        		}else{
        			if(r == len-1) return r+1;
        			if(A[r+1] >= target) return r+1;
    		    }
    	    }
    	    return 0;
        }
    }
    

    This algorithm is non deterministic so your results may vary...up the i counter to increase your accept chance (but dont make infinite loop).
    The idea is to see at what values of i you can consistently get accepted but by not doing an infinite loop.
    If you cant find it in the bounds of i then just return 0 and hope thats right!


  • 0
    B

    If you can figure it out, here are the quick optimizations:

    import java.util.Random;
    public class Solution {
       public int searchInsert(int[] A, int target) {
            Random rnd = new Random();
    	    int end = A.length;
        	int start = 0;
        	for(int i = 0; i < 30; i++){
        		int r = rnd.nextInt(((end-1) - start) + 1) + start;
        		if(A[r] == target) return r;
        		if(A[r] > target){
        			if(r == 0) return r;
        			if(A[r-1] == target) return r-1;
        			else if(A[r-1]< target) return r;
        			end = r+1;
        		}else{
        			if(r == end-1) return r+1;
        			if(A[r+1] >= target) return r+1;
        			start =r+1;
        		}
        	}
        	return rnd.nextInt(((end-1) - start) + 1) + start;
        }
    }
    

    With these optimizations we see that bounding i by 30 is more enough to get consistently accepted from the OJ. Why is that?

    I know this code is rather useless, but hopefully it teaches someone about the power of binary search!


Log in to reply
 

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