lintcode/median.cpp at master · deekookee/lintcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    //     int naive(vector<int> &nums) {
    //     // write your code here
    //     int n = nums.size();
    //     if (n == 0) {
    //         return 0;
    //     }
    //     sort(nums.begin(), nums.end());
    //     return nums[( n - 1 )/2];
    // }

    void swap(vector<int> &nums, int a, int b) {
    	int temp = nums[a];
    	nums[a]	= nums[b];
    	nums[b] = temp;
    }

    int findKSmall(vector<int> &nums, int k, int start, int end) {

    	int pivot = end;
    	int l = start;
    	int r = end;
    	while (true) {
    		while (nums[l] <= nums[pivot] && l < r) {
    			l++;
    		}
    		while (nums[pivot] <= nums[r] && l < r) {
    			r--;
    		}
    		if (r == l) break;
    		swap(nums, l, r);
    	}

    	swap(nums, l, pivot);

    	if (l == k) return nums[l];

    	if (l < k) return findKSmall(nums, k, l + 1, end);

    	return findKSmall(nums, k, start, l - 1);
    }


    int median(vector<int> &nums) {

    	int n = nums.size();
        if (n == 0) {
            return 0;
        }
        return findKSmall(nums, ( n - 1 )/2, 0, n - 1);
    }


};