谷歌一轮电面面经

给一个unsorted ar

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

k sort做

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

1. public static float findMedian(int []arr){
   
2.         if(arr.length %2 != 0){
   
3.             return odd(arr, 0, arr.length-1);
   
4.         }else{
   
5.             return even(arr, 0, arr.length-1);
   
6.         }
   
7.     }
   
8.     public static float odd(int []arr,int start ,int end){
   
9.         int pivot = Partition(arr,start,end);
   
10.         if(start < arr.length/2){
    
11.             return odd(arr, pivot+1, end);
    
12.         }
    
13.         if(start > arr.length/2){
    
14.             return odd(arr, start, pivot-1);
    
15.         }else return arr[pivot];
    
16.     }
    
17.     public static float even(int []arr,int start ,int end){
    
18.         if(start > end){
    
19.             return (arr[arr.length/2]+arr[arr.length/2-1])/2;
    
20.         }
    
21.         int pivot = Partition(arr,start,end);
    
22.         if(start <= arr.length/2-1) {
    
23.             return even(arr, pivot + 1, end);
    
24.         } else{
    
25.             return odd(arr, start, pivot-1);
    
26.         }
    
27.     }
    
28.     public void quicksort(int []arr,int start ,int end){
    
29.         if(start < end){
    
30.             int index = Partition(arr,start,end);
    
31.             quicksort(arr, start, index-1);
    
32.             quicksort(arr,index, end-1);
    
33.         }
    
34.     }
    
35.     public static int Partition(int []arr, int start, int end){
    
36.         int pivot = arr[start];
    
37.         while(start < end){
    
38.             while(start < end && pivot < arr[end]  ){
    
39.                 end--;
    
40.             }
    
41.             arr[start] = arr[end];
    
42.             while( start < end && arr[start]<= pivot ){
    
43.                 start++;
    
44.             }
    
45.             arr[end] = arr[start];
    
46.         }
    
47.         arr[start] = pivot;
    
48.         return start;
    
49.     }

复制代码

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

请问楼主一开始用什么方法做的呢？