• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Feb 24th, 2019 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <limits>
4. #include <algorithm>
5.
6. using namespace std;
7.
8. // Find the median of a vector<int>
9.
10. void PrintVector(const vector<int>& nums) {
11.     for (int i = 0; i < nums.size(); ++i)
12.         std::cout << nums[i] << " ";
13.     std::cout << std::endl;
14. }
15.
16. int MedianUtil(vector<int>& nums, int left, int right, int k) {
17.
18.     if (k > 0 && k <= (right - left + 1)) {
19.
20.         int pivot = nums[right];
21.         int j = left - 1;
22.         for (int i = left; i <= right - 1; ++i) {
23.             if (nums[i] <= pivot) {
24.                 ++j;
25.                 swap(nums[i], nums[j]);
26.             }
27.         }
28.         ++j;
29.         swap(nums[j], nums[right]);
30.
31.         if (j - left == k - 1)
32.             return nums[j + 1];
33.         if (j - left > k - 1)
34.             return MedianUtil(nums, left, j - 1, k);
35.
36.         return MedianUtil(nums, j + 1, right, k - j + left - 1);
37.     }
38.
39.     return numeric_limits<int>::min();
40. }
41.
42. /*
43. int Median(vector<int>& nums) {
44.     return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);
45. }
46. */
47.
48. int Median(vector<int>& nums) {
49.     nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end(), [](const int p1, const int p2){return (p1 < p2);});
50.     return(nums[nums.size() / 2]);
51. }
52.
53. int main()
54. {
55.     vector<int> nums{3, 2, 1, 6, 6};
56.
57.     PrintVector(nums);
58.
59.     std::cout << Median(nums) << std::endl;
60.
61.     return 0;
62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?