Median

Question

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.

Thoughts

这一题要求O(n)，我们可以想到用quick select的做法

注意点

quick select的做法也要加入考虑有重复元素的情况 我们这里加入一个foundPivot的boolean 如果第一次发现pivot，就设为true,之后遇到的所有pivot都当做小于处理

Solution

import random
class Solution:
    """
    @param nums: A list of integers.
    @return: An integer denotes the middle number of the array.
    """
    def median(self, nums):
        # write your code here
        if not nums:
            return None
        length = len(nums)
        mid = length / 2 + 1
        return self.kthLargestElement(mid, nums)

    def kthLargestElement(self, k, A):
        pivot = random.choice(A)
        numSmaller = 0
        length = len(A)
        foundPivot = False
        for idx, num in enumerate(A):
            if num < pivot:
                tmp = A[numSmaller]
                A[numSmaller] = num
                A[idx] = tmp
                numSmaller += 1
            elif num == pivot:
                if foundPivot:
                    tmp = A[numSmaller]
                    A[numSmaller] = num
                    A[idx] = tmp
                    numSmaller += 1
                else:
                    foundPivot = True
        if k < length - numSmaller:
            return self.kthLargestElement(k, A[numSmaller:])
        elif k > length - numSmaller:
            return self.kthLargestElement(k - length + numSmaller, A[:numSmaller])
        return pivot