# Median

## Question

### Problem Statement

Given a unsorted array with integers, find the median of it.

A median is the middle number of the array after it is sorted.

If there are even numbers in the array, return the N/2-th number after sorted.

#### Example

Given [4, 5, 1, 2, 3], return 3.

Given [7, 9, 4, 5], return 5.

#### Challenge

$O(n)$ time.

## 题解

### Python

class Solution:
"""
@param nums: A list of integers.
@return: An integer denotes the middle number of the array.
"""
def median(self, nums):
if not nums:
return -1
return self.kth(nums, 0, len(nums) - 1, (1 + len(nums)) / 2)

def kth(self, nums, left, right, k):
# if left >= right: return nums[right]

m = left
for i in xrange(left + 1, right + 1):
if nums[i] < nums[left]:
m += 1
nums[m], nums[i] = nums[i], nums[m]

# swap between m and l after partition, important!
nums[m], nums[left] = nums[left], nums[m]

if m + 1 == k:
return nums[m]
elif m + 1 > k:
return self.kth(nums, left, m - 1, k)
else:
return self.kth(nums, m + 1, right, k)


### C++

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
int median(vector<int> &nums) {
if (nums.empty()) return 0;

int len = nums.size();
return kth(nums, 0, len - 1, (len + 1) / 2);
}

private:
int kth(vector<int> &nums, int left, int right, int k) {
// if (left >= right) return nums[right];

int m = left; // index m to track pivot
for (int i = left + 1; i <= right; ++i) {
if (nums[i] < nums[left]) {
++m;
std::swap(nums[i], nums[m]);
}
}

// swap with the pivot
std::swap(nums[left], nums[m]);

if (m + 1 == k) {
return nums[m];
} else if (m + 1 > k) {
return kth(nums, left, m - 1, k);
} else {
return kth(nums, m + 1, right, k);
}
}
};


### Java

public class Solution {
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public int median(int[] nums) {
if (nums == null || nums.length == 0) return -1;

return kth(nums, 0, nums.length - 1, (nums.length + 1) / 2);
}

private int kth(int[] nums, int left, int right, int k) {
// if (left >= right) return nums[right];

int m = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < nums[left]) {
m++;
swap(nums, i, m);
}
}
// put pivot in the mid position
swap(nums, left, m);

if (k == m + 1) {
return nums[m];
} else if (k > m + 1) {
return kth(nums, m + 1, right, k);
} else {
return kth(nums, left, m - 1, k);
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}