Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
FindMedian
/*Find Median in Large Integer File of Integers Find the median from a large file of integers. You can not access the numbers by index, can only access it sequentially. And the numbers cannot fit in memory. */ #include<vector> #include <iostream> #include <limits.h> using namespace std; int find(vector<int>& v, int countTarget, long left, long right){ // the mid must ex //if(left>= right) return left; int guess = (left+right)/2; int count = 0; int res = left; // guessing the mid for(auto x: v){ if(x <= guess) { count++; res = max(res,x); } } if(count == countTarget) return res; // found countTarget number if(count < countTarget){ res = find(v, countTarget, max(res+1, guess), right); } else{ res = find(v, countTarget, left, res); } return res; } double findMid(vector<int>& v){ int N = 0; for(auto x: v) N++; if(N%2) //odd return find(v, N/2 + 1, INT_MIN, INT_MAX); else{ int x = find(v, N/2 , INT_MIN, INT_MAX); int y = find(v, N/2 + 1, INT_MIN, INT_MAX); return (x+y)/2.0; } return 0; } int main() { vector<int> v = {1,2,3}; double m = findMid(v); cout << "m(2.0) = " << m << endl; v = {1,2,3,4}; cout << "m(2.5) = " << findMid(v) << endl; v = {1}; cout << "m(1) = " << findMid(v) << endl; }
run
|
edit
|
history
|
help
0
Second program
134
Запаковать строку в JSON (Boost)
Subset sum
Connected components in complement graph
cache_node.cc
POI
Kth smallest element
simple use of templete
Test 1(2021)