谷歌一轮电面面经

Job Hunting Interview
, , , , , ,
1

给一个unsorted array， 要求找出中位数。follow up让用recursive的quick sort做

2

找中位数不应该是quick select更快吗？

3 
public static float findMedian(int []arr){
        if(arr.length %2 != 0){
            return odd(arr, 0, arr.length-1);
        }else{
            return even(arr, 0, arr.length-1);
        }
    }
    public static float odd(int []arr,int start ,int end){
        int pivot = Partition(arr,start,end);
        if(start < arr.length/2){
            return odd(arr, pivot+1, end);
        }
        if(start > arr.length/2){
            return odd(arr, start, pivot-1);
        }else return arr[pivot];
    }
    public static float even(int []arr,int start ,int end){
        if(start > end){
            return (arr[arr.length/2]+arr[arr.length/2-1])/2;
        }
        int pivot = Partition(arr,start,end);
        if(start <= arr.length/2-1) {
            return even(arr, pivot + 1, end);
        } else{
            return odd(arr, start, pivot-1);
        }
    }
    public void quicksort(int []arr,int start ,int end){
        if(start < end){
            int index = Partition(arr,start,end);
            quicksort(arr, start, index-1);
            quicksort(arr,index, end-1);
        }
    }
    public static int Partition(int []arr, int start, int end){
        int pivot = arr[start];
        while(start < end){
            while(start < end &amp;&amp; pivot < arr[end]  ){
                end--;
            }
            arr[start] = arr[end];
            while( start < end &amp;&amp; arr[start]<= pivot ){
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }

补充内容 (2018-11-18 00:52):
大概这样？lz