• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Feb 23rd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /******************************************************************************
2.
3.                               Online C++ Compiler.
4.                Code, Compile, Run and Debug C++ program online.
5. Write your code in this editor and press "Run" button to compile and execute it.
6.
7. *******************************************************************************/
8.
9. #include <iostream>
10. #include <vector>
11. #include <limits>
12.
13. using namespace std;
14.
15. // Find k largest element (k = n/2)
16.
17. void PrintVector(const vector<int>& nums) {
18.     for (int i = 0; i < nums.size(); ++i) {
19.         std::cout << nums[i] << " ";
20.     }
21.     std::cout << std::endl;
22. }
23.
24. int MedianUtil(vector<int>& nums, int left, int right, int k) {
25.
26.     if (k > 0 && k <= (right - left + 1)) {
27.
28.         int pivot = nums[right];
29.         int j = left - 1;
30.         for (int i = left; i <= right - 1; ++i) {
31.             if (nums[i] <= pivot) {
32.                 ++j;
33.                 swap(nums[i], nums[j]);
34.             }
35.         }
36.         ++j;
37.         swap(nums[j], nums[right]);
38.
39.         if (j - left == k - 1)
40.             return nums[j];
41.         if (j - left > k - 1)
42.             return MedianUtil(nums, left, j - 1, k);
43.
44.         return MedianUtil(nums, j + 1, right, k - j + left - 1);
45.     }
46.
47.     return numeric_limits<int>::min();
48. }
49.
50. int Median(vector<int>& nums) {
51.
52.     return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);
53.
54. }
55.
56. int main()
57. {
58.     vector<int> nums{0,2,3,1,6,4};
59.     // 1 1 2 2 3 6
60.     PrintVector(nums);
61.
62.     std::cout << Median(nums) << std::endl;
63.
64.     return 0;
65. }
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.

Top