首页 > 代码库 > 【HackerRank】Find the Median(Partition找到数组中位数)
【HackerRank】Find the Median(Partition找到数组中位数)
In the Quicksort challenges, you sorted an entire array. Sometimes, you just need specific information about a list of numbers, and doing a full sort would be unnecessary. Can you figure out a way to use your partition code to find the median in an array?
Challenge
Given a list of numbers, can you find the median?
Input Format
There will be two lines of input:
- n - the size of the array
- ar - n numbers that makes up the array
Output Format
Output one integer, the median.
Constraints
1<= n <= 1000001
-10000 <= x <= 10000 , x ∈ ar
There will be an odd number of elements.
题解：久闻Partition函数可以用来找到乱序数组的中位数，今天终于实现了一把。
设置一个变量need为数组长度的一半，另一个变量hasFound为当前比找到的比中位数小的数的个数，当hasFound=need的时候，我们就找到了中位数。
在每次Partition后，看比pivot小的那部分数组有多少个元素，如果hasFound加上这部分元素正好等于need，那么pivot就是所求的中位数。如果hasFound加上这部分元素大于need，说明比pivot小的这部分数组需要继续划分，递归的调用Partition；如果hasFound加上这部分元素小于need，那么就把这部分元素个数加到hasFound上，并且继续划分比pivot大的那部分数组。
例如数组：3 1 4 5 2，找中位数的过程如下图所示：
代码如下：
1 import java.util.*; 2 3 public class Solution { 4 private static int need = 0; 5 private static int hasFound = 0; 6 7 private static void swap(int[] ar,int i,int j){ 8 int temp = ar[i]; 9 ar[i]= ar[j];10 ar[j]=temp;11 }12 private static int Partition(int[] ar,int start,int end){13 int pivot = ar[end];14 int i = start;15 int j = start;16 while(i < end){17 if(ar[i] >= pivot)18 i++;19 else if(ar[i] < pivot){20 swap(ar,i,j);21 i++;22 j++;23 }24 }25 swap(ar, j, end);26 if(hasFound+j-start+1==need)27 return pivot;28 else if(hasFound+j-start+1<need){29 hasFound += j-start+1;30 return Partition(ar, j+1, end);31 }32 else {33 return Partition(ar, start, j-1);34 }35 36 }37 38 public static void main(String[] args) {39 Scanner in = new Scanner(System.in);40 int n = in.nextInt();41 need = n%2==0?n/2:n/2+1;42 int[] ar = new int[n];43 44 for(int i = 0;i < n;i ++)45 ar[i] = in.nextInt();46 System.out.println(Partition(ar, 0, n-1));47 48 }49 }
以上代码就很容易扩展到找寻数组中第k小的数了，只要改变need变量的值即可。