描述

给定一个未排序的整数数组，找到其中位数。

中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

数组大小不超过10000

样例

样例 1:

输入：[4, 5, 1, 2, 3]
输出：3
解释：
经过排序，得到数组[1,2,3,4,5]，中间数字为3

样例 2:

输入：[7, 9, 4, 5]
输出：5
解释：
经过排序，得到数组[4,5,7,9]，第二个(4/2)数字为5

挑战（√）

时间复杂度为O(n)

编程语言：Java

解题思想：

1.直接调用排序的api。

2.根据数组为奇数/偶数判断中位数的位置。

时间复杂度：O(1)

IDE代码如下：

package LintCode_Easy;
 
import java.util.Arrays;
 
public class _80 {
 
	public static void main(String[] args) {
		int[] nums = new int[] {4,5,1,2,3};
		Arrays.sort(nums);
		if(nums.length%2==0) 
		System.out.println(nums[nums.length/2-1]);
		else
		System.out.println(nums[nums.length/2]);
	}
 
}
 

LintCode编辑器代码如下：

public class Solution {
    public int median(int[] nums) {
        Arrays.sort(nums);
		if(nums.length%2==0) 
		return nums[nums.length/2-1];
		else
		return nums[nums.length/2];
    }
}