Go divide and conquer


  • 0
    D
    func missingNumber(nums []int) int {
    	return minfrom(0, len(nums), nums)
    }
    func partition(xs []int, num int) (us, vs []int) {
    	us = make([]int, 0)
    	vs = make([]int, 0)
    	for _, e := range xs {
    		if (e < num) {
    			us = append(us, e)
    		} else {
    			vs = append(vs, e)
    		}
    	}
    	return
    
    }
    
    func minfrom(a int, n int, xs []int) int {
    	b := a + 1 + n / 2
    	us, vs := partition(xs, b)
    	m := len(us)
    	if (n == 0) {
    		return a
    	} else if (m == b - a) {
    		return minfrom(b, n - m, vs)
    	} else {
    		return minfrom(a, m, us)
    	}
    }
    

Log in to reply
 

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